1. question: 二叉树的最近公共祖先（中等）
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
示例 1：
1
2
3
| 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
|
示例 2：
1
2
3
| 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
|
示例 3：
1
2
| 输入：root = [1,2], p = 1, q = 2
输出：1
|
提示：
1
2
3
4
5
| 树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
|
2. answers
这道题注意不要限制思维，还要注意利用二叉树的递归特性。
两个节点的祖先，换个思路想就是祖先的两个子树包含pq。如果左右子树包含了pq节点，那么就说明当前节点是公共祖先。或者左右子树任意一个包含了pq节点，并且当前节点是pq其中一个，也说明当前节点就是公共祖先。并且，因为是最近公共祖先，所以采取自底向上的方式，递归的方法最直接。另外，因为要判断左右节点，最好是采用后序遍历。并且当前节点也有可能是pq，所以需要注意，当前节点也需要判断。
感觉无论这么样，最终还是回归到二叉树的递归特性：子树仍然是二叉树。
代码如下所示：
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
public class Solution_0071 {
public boolean tag;
public TreeNode postOrder(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
TreeNode left = postOrder(root.left, p, q);
TreeNode right = postOrder(root.right, p, q);
if(tag) return left == null ? right : left;
if((root.val == p.val || root.val == q.val) && (left != null || right != null)) {
tag = true;
return root;
}
if(root.val == p.val || root.val == q.val) {
return root;
}
if(left != null && right != null) {
tag = true;
return root;
}
if(left != null) return left;
else return right;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return postOrder(root, p, q);
}
public static void main(String[] args) {
System.out.println();
TreeNode tn9 = new TreeNode(4);
TreeNode tn8 = new TreeNode(7);
TreeNode tn7 = new TreeNode(8);
TreeNode tn6 = new TreeNode(0);
TreeNode tn5 = new TreeNode(2, tn8, tn9);
TreeNode tn4 = new TreeNode(6);
TreeNode tn3 = new TreeNode(1, tn6, tn7);
TreeNode tn2 = new TreeNode(5, tn4, tn5);
TreeNode tn1 = new TreeNode(3, tn2, tn3);
Solution_0071 s = new Solution_0071();
TreeNode p = new TreeNode(5);
TreeNode q = new TreeNode(4);
TreeNode res = s.lowestCommonAncestor(tn1, p, q);
System.out.println(res.val);
}
}
|
参考题解，简化后的代码如下所示：
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
|
public class Solution_0071_02 {
public TreeNode postOrder(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = postOrder(root.left, p, q);
TreeNode right = postOrder(root.right, p, q);
if(left == null && right == null) return null;
else if(left == null && right != null) return right;
else if(left != null && right == null) return left;
else return root;
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
