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

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

递归解法

• 时间复杂度
  O(n) 其中 N 是二叉树的节点数，所有节点都会被访问一次。
• 空间复杂度
  O(n) 其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。

var commTree: TreeNode?

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil }
        _ = dfs(root, p, q)
        return commTree
    }

    func dfs(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> Bool {
        guard let root = root else { return false }
        // 左子树是否包含 q 或 q
        let lson = dfs(root.left, p, q)
        // 右子树是否包含 q 或 q
        let rson = dfs(root.right, p, q)
        // 左右子树包含pq || (左子树或右子树包含 且 当前root.val == p.val 或 q.val)
        if (lson && rson) || ((lson || rson) && (root.val == p?.val || root.val == q?.val)) {
            commTree = root
        }
        // 如果包含 p q, 会先命中 root.val == p?.val || root.val == q?.val
        // 这时返回的值是 true, 后面 会命中 lson || rson
        return root.val == p?.val || root.val == q?.val || lson || rson
    }