二叉树最近公共祖先 (opens in a new tab)
分类讨论
返回当前节点的情况
- 当前节点是空节点
- 当前节点是 p
- 当前节点是 q
其他
- 左右子树都找到：返回当前节点
- 只有左子树找到：返回递归左子树的结果
- 只有右子树找到：返回递归右子树的结果
- 左右子树都没有找到：返回空节点
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode | null,
q: TreeNode | null,
): TreeNode | null {
if (!root || p === root || q === root) {
return root;
}
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) {
return root;
}
if (left) return left;
return right;
}