forked from algorithm010/algorithm010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLC236_lowest_common_ancestor.java
More file actions
40 lines (35 loc) · 1.42 KB
/
LC236_lowest_common_ancestor.java
File metadata and controls
40 lines (35 loc) · 1.42 KB
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
package Week03;
public class LC236_lowest_common_ancestor {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
/*
* 具体思路：
（1） 如果当前结点 root 等于 NULL，则直接返回 NULL
（2） 如果 root 等于 p 或者 q ，那这棵树一定返回 p 或者 q
（3） 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 left 和 right 表示
（4） 此时若left为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left
（5） 如果 left 和 right 都非空，因为只给了 p 和 q 两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先
（6） 如果 left 和 right 都为空，则返回空（其实已经包含在前面的情况中了）
* */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){
return null;
}
if (root == p || root == q) return root; // 本身是祖先
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if (left == null){ //左边没有两个都在右边
return right;
}
if (right == null){ //右边没有两个都在左边
return left;
}
//一边一个
return root;
}
/**/
}