[!info] related notes 算法面试题型 MOC 二叉树高频题

Lowest Common Ancestor in Binary Tree

LeetCode: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

本题保证 p、q 是树内两个不同节点，按对象身份比较而不是按值查找。节点可以是自己的祖先，所以当 p 是 q 的祖先时结果就是 p；不要求树是二叉搜索树。

思路

对每个节点 root，递归返回以下几种状态之一：

• null：当前子树没有找到 p/q
• 非空节点：可能是找到的 p/q，也可能是子树内已确定的公共祖先
• 左右返回均非空时，当前 root 连接两条目标路径；只有一侧非空时继续向上传递

递归规则：

• root == null => return null
• root == p || root == q => return root
• left = dfs(root.left), right = dfs(root.right)
  • left != null && right != null => return root
  • 否则 return left ?? right

代码（JavaScript）

var lowestCommonAncestor = function(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 && right) return root;
  return left ?? right;
};

时间 O(n)，递归栈 O(h)。若取消“两个目标都存在”的前提，这段代码可能只返回唯一存在的目标，不能据此宣称公共祖先已找到；需要额外验证存在性。

Related

• 二叉树高频题