給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)節(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)節(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）?！?br> LeetCode：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree

image.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        // 到底了
        guard let root = root else { return nil }
        
        // 前序位置：遇到目標(biāo)值就可以返回了，不必再向下
        if root === p || root === q {
            return root
        }
        let left  = lowestCommonAncestor(root.left,  p, q)
        let right = lowestCommonAncestor(root.right, p, q)

        // 后序位置：已經(jīng)知道了左右子樹(shù)是否有目標(biāo)節(jié)點(diǎn)
        // 如果該節(jié)點(diǎn)左右子樹(shù)都有目標(biāo)值，說(shuō)明該節(jié)點(diǎn)是最近公共祖先
        if left != nil, right != nil {
            return root
        }

        // 只有左子樹(shù)或右子樹(shù)有目標(biāo)節(jié)點(diǎn)
        return left ?? right
    }
}

image.png