二叉树的最近公共祖先
🟡 中等题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。“
示例 1
输入：root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3示例 2
输入：root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5提示
- 树中节点数目在范围
[2, 10^5]内 -10^9 <= Node.val <= 10^9- 所有
Node.val互不相同 p != qp和q均存在于给定的二叉树中
解法
参考答案 (3 个标签)
递归 后序遍历 O(n)
思路
后序遍历，对于每个节点：
- 如果当前节点是 p 或 q，返回当前节点
- 在左右子树中查找 p 和 q
- 如果左右子树都找到了，当前节点就是 LCA
- 如果只有一边找到，返回找到的那一边
代码实现
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
function lowestCommonAncestor(root, p, q) {
if (root === null || root === p || root === q) {
return root;
}
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left !== null && right !== null) {
return root;
}
return left !== null ? left : right;
}复杂度分析
- 时间复杂度：O(n)，最坏情况遍历所有节点
- 空间复杂度：O(h)，递归栈深度
图解
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
找 5 和 1 的 LCA：
- 节点 5 返回 5（找到 p）
- 节点 1 返回 1（找到 q）
- 节点 3 左右都不为空，返回 3