235. 二叉搜索树的最近公共祖先
题目描述
输入一棵二叉搜索树的根节点 root，以及树中两个不同的节点 p 和 q。树用层序数组表示，空位记为 null；p、q 用节点值给出。
若节点 x 既是 p 的祖先，又是 q 的祖先，就称它为二者的公共祖先。一个节点也算作它自己的祖先。在所有公共祖先中，深度最大的那个就是最近公共祖先。
返回 p 和 q 的最近公共祖先。
示例 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
解释：4 位于 2 的子树中，而节点自身也算祖先，所以答案是 2。
示例 3
输入：root = [2,1], p = 2, q = 1 输出：2
解释：1 是 2 的左孩子，节点 2 自身就是最近公共祖先。
数据范围
- 所有节点的值各不相同。
p != qp和q都在这棵树中。
解题思路：一次遍历找分叉点
利用 BST 的有序性从根往下走。如果 p、q 都比当前节点小，它们都在左子树，公共祖先也在左边；都比它大则往右。否则两者分居两侧，或者其中一个就是当前节点，当前节点就是最近公共祖先。
为什么正确
循环中 node 始终是 p 和 q 的公共祖先。
复杂度分析
时间 O(h)，空间 O(1)。
易错点
判断“往左”“往右”时要用严格的小于和大于。p 或 q 等于当前节点时，当前节点就是答案，不能再往下走。这个做法只适用于 BST，普通二叉树要用 236 的递归。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
node = root
while node:
if p.val < node.val and q.val < node.val:
node = node.left
elif p.val > node.val and q.val > node.val:
node = node.right
else:
return nodeclass Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode node = root;
while (node != null) {
if (p.val < node.val && q.val < node.val) {
node = node.left;
} else if (p.val > node.val && q.val > node.val) {
node = node.right;
} else {
return node;
}
}
return null;
}
}class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* node = root;
while (node) {
if (p->val < node->val && q->val < node->val) {
node = node->left;
} else if (p->val > node->val && q->val > node->val) {
node = node->right;
} else {
return node;
}
}
return nullptr;
}
};func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
node := root
for node != nil {
if p.Val < node.Val && q.Val < node.Val {
node = node.Left
} else if p.Val > node.Val && q.Val > node.Val {
node = node.Right
} else {
return node
}
}
return nil
}var lowestCommonAncestor = function(root, p, q) {
let node = root;
while (node) {
if (p.val < node.val && q.val < node.val) {
node = node.left;
} else if (p.val > node.val && q.val > node.val) {
node = node.right;
} else {
return node;
}
}
return null;
};function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
let node: TreeNode | null = root;
while (node) {
if (p!.val < node.val && q!.val < node.val) {
node = node.left;
} else if (p!.val > node.val && q!.val > node.val) {
node = node.right;
} else {
return node;
}
}
return null;
}其他解法
两种方法都利用了二叉搜索树的有序性，时间都是 O(h)。一次遍历把两条路径合并走，在分叉处停下，省掉了路径数组。
解法 2：两次遍历比较路径 时间 O(h)，空间 O(h)
利用二叉搜索树的性质，分别从根走到 p 和 q，记录两条路径上的节点。从头同时比较两条路径，最后一个相同的节点就是最近公共祖先。
思路直观，容易说明正确性。需要存两条路径，占 O(h) 空间，还要遍历两次。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def get_path(target):
path = []
node = root
while node is not target:
path.append(node)
node = node.left if target.val < node.val else node.right
path.append(node)
return path
pp, pq = get_path(p), get_path(q)
ans = root
for a, b in zip(pp, pq):
if a is not b:
break
ans = a
return ansclass Solution {
private List<TreeNode> getPath(TreeNode root, TreeNode target) {
List<TreeNode> path = new ArrayList<>();
TreeNode node = root;
while (node != target) {
path.add(node);
node = target.val < node.val ? node.left : node.right;
}
path.add(node);
return path;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pp = getPath(root, p), pq = getPath(root, q);
TreeNode ans = root;
for (int i = 0; i < pp.size() && i < pq.size(); i++) {
if (pp.get(i) != pq.get(i)) break;
ans = pp.get(i);
}
return ans;
}
}class Solution {
vector<TreeNode*> getPath(TreeNode* root, TreeNode* target) {
vector<TreeNode*> path;
TreeNode* node = root;
while (node != target) {
path.push_back(node);
node = target->val < node->val ? node->left : node->right;
}
path.push_back(node);
return path;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pp = getPath(root, p), pq = getPath(root, q);
TreeNode* ans = root;
for (size_t i = 0; i < pp.size() && i < pq.size(); i++) {
if (pp[i] != pq[i]) break;
ans = pp[i];
}
return ans;
}
};func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
getPath := func(target *TreeNode) []*TreeNode {
path := []*TreeNode{}
node := root
for node != target {
path = append(path, node)
if target.Val < node.Val {
node = node.Left
} else {
node = node.Right
}
}
return append(path, node)
}
pp, pq := getPath(p), getPath(q)
ans := root
for i := 0; i < len(pp) && i < len(pq); i++ {
if pp[i] != pq[i] {
break
}
ans = pp[i]
}
return ans
}var lowestCommonAncestor = function(root, p, q) {
const getPath = (target) => {
const path = [];
let node = root;
while (node !== target) {
path.push(node);
node = target.val < node.val ? node.left : node.right;
}
path.push(node);
return path;
};
const pp = getPath(p), pq = getPath(q);
let ans = root;
for (let i = 0; i < pp.length && i < pq.length; i++) {
if (pp[i] !== pq[i]) break;
ans = pp[i];
}
return ans;
};function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
const getPath = (target: TreeNode): TreeNode[] => {
const path: TreeNode[] = [];
let node = root!;
while (node !== target) {
path.push(node);
node = (target.val < node.val ? node.left : node.right)!;
}
path.push(node);
return path;
};
const pp = getPath(p!), pq = getPath(q!);
let ans = root;
for (let i = 0; i < pp.length && i < pq.length; i++) {
if (pp[i] !== pq[i]) break;
ans = pp[i];
}
return ans;
}