Lowest Common Ancestor in Binary Tree

LeetCode 236 二叉树最近公共祖先：递归分类讨论模板。

#resource / algorithm #type / howto #status / evergreen #ds / tree #algo / recursion #source / leetcode

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

Lowest Common Ancestor in Binary Tree

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

思路

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

null：当前子树没有找到 p/q
p 或 q：当前子树找到了其中一个
root：左右子树分别找到了 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;
};

二叉树高频题