Skip to main content

236. Lowest Common Ancestor of a Binary Tree

分析


https://mp.weixin.qq.com/s/9RKzBcr3I592spAsuMH45g

题解

/**
题目保证了一定存在,但递归过程中还有2、3的情况
1. p q 都在 root 下,返回距离最近的 公共节点
2. p q 其中一个在 返回在的节点 p || q
3. p q 均不在 返回 null
*/
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
if (root === null) {
return null
}
if (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 ? right : left
};