1. 题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a
-binary-search-tree/
Related Topics 树
2. 题解
2.1 解法1: 迭代(一次遍历)
从根节点开始遍历；
- 如果当前节点的值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
- 如果当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
- 如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点。
相当于找分岔点
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) {
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
break;
}
}
return root;
}
}
2.2 解法2: 递归
思路同解法1
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
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;
}
}
}
2.3 解法3: 两次遍历
由于是二叉搜索树, 根节点大于左节点, 小于右节点,
- 第一次遍历查找 p 的位置, 第二次查找q, 同时记录路径
- 最后找到两条路径中最后一个相同的结点即为最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
List<TreeNode> pList = new ArrayList<>();
List<TreeNode> qList = new ArrayList<>();
TreeNode curr = root;
while (curr != p) {
pList.add(curr);
if (p.val < curr.val) {
curr = curr.left;
} else if (p.val > curr.val) {
curr = curr.right;
}
}
pList.add(curr);
curr = root;
while (curr != q) {
qList.add(curr);
if (q.val < curr.val) {
curr = curr.left;
} else if (q.val > curr.val) {
curr = curr.right;
}
}
qList.add(curr);
TreeNode ans = null;
for (int i = 0; i < pList.size() && i < qList.size(); i++) {
if (pList.get(i) == qList.get(i)) {
ans = pList.get(i);
} else {
break;
}
}
return ans;
}
}