FilesExpand file tree

 master

/

offer68.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

41 lines (39 loc) · 1.31 KB

 master

/

offer68.java

Copy path

Top

File metadata and controls

• Code
• Blame

41 lines (39 loc) · 1.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

/**

* [68-I] 二叉搜索树的最近公共祖先

*

* 题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先.

* (所有节点的值都是唯一的; p, q 为不同节点且均存在于给定的二叉搜索树中.)

*

* 思路: 利用二叉搜索树的特性来判断当前节点是否为公共祖先, 并向可能有公共祖先节点的方向遍历.

* 两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val.

*/

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

/**

* 时间复杂度: O(n)

* 空间复杂度: O(n)

*/

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null) {

return null;

}

// if both p and q are greater than parent.

if (root.val > p.val && root.val > q.val) {

return lowestCommonAncestor(root.left, p, q);

}

// if both p and q are lesser than parent.

if (root.val < p.val && root.val < q.val) {

return lowestCommonAncestor(root.right, p, q);

}

// we have found the split point, i.e. the LCA node.

return root;

}

}