难度 简单
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
1
2
3
4
5
6
7
| _______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
|
示例 1:
1
2
3
| **输入:** root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
**输出:** 6
**解释:** 节点 2 和节点 8 的最近公共祖先是 6。
|
示例 2:
1
2
3
| **输入:** root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
**输出:** 2
**解释:** 节点 `2` 和节点 `4` 的最近公共祖先是 `2`, 因为根据定义最近公共祖先节点可以为节点本身。
|
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
Solution
解法1，自顶向下遍历
我们可以从根结点出发，判断当前结点的左右子树是否包含这两个结点。如果左子树包含两个结点，则它们的最低公共祖先结点也一定在左子树中。如果右子树包含两个结点，则它们的最低公共祖先结点也一定在右子树中。如果一个结点在左子树，而另一个结点在右子树中，则当前结点就是它们的最低公共祖先结点。根据该思路写出代码如下，注意这里已经假定p和q是二叉树中的结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return null;
if (containTargetTreeNode(root.left, p) && containTargetTreeNode(root.left, q)){
return lowestCommonAncestor(root.left, p, q);
}else if (containTargetTreeNode(root.right, p) && containTargetTreeNode(root.right, q)){
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
private boolean containTargetTreeNode(TreeNode root, TreeNode targetNode) {
if (root == null)
return false;
if (root == targetNode)
return true;
return containTargetTreeNode(root.left, targetNode) || containTargetTreeNode(root.right, targetNode);
}
|
思路二：自顶向上
由于自顶向下的方法需要重复遍历结点，使用自底向上的方法可以避免这种情况。
自底向上遍历结点，一旦遇到结点等于p或者q，则将其向上传递给它的父结点。父结点会判断它的左右子树是否都包含其中一个结点，如果是，则父结点一定是这两个节点p和q的LCA，传递父结点到root。如果不是，我们向上传递其中的包含结点p或者q的子结点，或者NULL(如果子结点不包含任何一个)。该方法时间复杂度为O(N)。
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
if (root == null)
return null;
if (p == root || q == root)
return root;
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
if (l != null && r != null)
return root;
return l == null ? r : l;
}
}
|
思路三：利用搜索树的性质
因为树是二叉树，我们从根节点开始遍历，一定有顶点root的值大于p和q的值时，p、q的最近祖先一定在root的左子树下，当root的值小于p、q的值时，那么p、q的最近祖先一定在root的左子树下，不是上述两种情况的话，说明当前的root已经是最近的祖先了。
1
2
3
4
5
6
7
8
9
| public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q){
if (root == null)
return null;
if (root.val > p.val && root.val > q.val)
return lowestCommonAncestor3(root.left, p, q);
else if (root.val < p.val && root.val < q.val)
return lowestCommonAncestor3(root.right, p, q);
return root;
}
|