-
Notifications
You must be signed in to change notification settings - Fork 0
/
LCA.java
65 lines (61 loc) · 1.87 KB
/
LCA.java
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
// write your code here
if(root == null){
return null;
}
if(root.equals(A) || root.equals(B)){
return root;
}
//相当于你去左边找A,右边找B
// 如果两边都找到,则说明最初的root是LCA
// 如果一边为NULL,则说明A AND B在同一边,返回不为NULL的一边即可
TreeNode left = lowestCommonAncestor(root.left, A, B);
TreeNode right = lowestCommonAncestor(root.right, A, B);
if(left != null && right != null){
return root;
}
return left != null ? left : right;
}
}
// Situation change to BST, it becomes easy
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(p.equals(root) || q.equals(root)){
return root;
}
if(p.val < root.val && q.val < root.val){
return lowestCommonAncestor(root.left, p, q);
}else if(p.val > root.val && q.val > root.val){
return lowestCommonAncestor(root.right, p, q);
}else{
return root;
}
}
}