236. 二叉树的最近公共祖先

[Geekhyt]

原题链接

递归 dfs

1.从根节点开始遍历，递归左右子树
2.递归终止条件：当前节点为空或者等于 p 或 q，返回当前节点
3.p，q 可能在相同的子树中，也可能在不同的子树中
4.如果左右子树查到节点都不为空，则表示 p 和 q 分别在左右子树中，当前节点就是最近公共祖先
5.如果左右子树中有一个不为空，则返回为空节点

const lowestCommonAncestor = function(root, p, q) {
    if (root === null || root === p || root === q) return root

    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)

    if (left !== null && right !== null) {
        return root
    }

    return left !== null ? left : right
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)