关于算法:leetcode-236-二叉树的最近公共祖先

题目:

给定一个二叉树, 找到该树中两个指定节点的最近公共先人。

最近公共先人的定义为：“对于有根树 T 的两个节点 p、q，最近公共先人示意为一个节点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。”

递归解决:

func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let n = root, let lhs = p, let rhs = q else {return nil}
        if n.val == lhs.val || n.val == rhs.val{return n}
        let left = lowestCommonAncestor(n.left, p, q)
        let right = lowestCommonAncestor(n.right, p, q)
        if left == nil{return right}
        if right == nil{return left}
        return n
    }

阐明:

肯定存在根节点，

找到了一个，就不会持续往下找了，这条线（右边的）断了，

就只看左边找不找失去。

左边找到了，根结点

左边找不到，残余的，在右边没有去找的结点中

有两个点，找到了，就打住

所以不会有一个点，反复命中

递归的个性，是自底部向上

带入过程

带入一

3

右边，5，找到了，返回 5，右边进行拜访

左边，1，找到了，返回 1，左边进行拜访

result 是 root

带入 2

3

右边，5，找到了，返回 5，右边进行拜访

左边，1，去寻找

1

右边 0，不是，返回 nil，进行拜访

左边 8，不是，返回 nil，进行拜访

第一步的递归调用出后果

3

右边，5，找到了

左边，nil, 没找到

result 是右边

辅助测试代码:

        let three = TreeNode(3)
        let five = TreeNode(5)
        let one = TreeNode(1)
        
        let six = TreeNode(6)
        let two = TreeNode(2)
        let zero = TreeNode(0)
        let eight = TreeNode(8)
        
        let seven = TreeNode(7)
        let four = TreeNode(4)
        
        three.left = five
        three.right = one
        
        five.left = six
        five.right = two
        
        one.left = zero
        one.right = eight
        
        two.left = seven
        two.right = four
        let result = Solution().lowestCommonAncestor(three, five, one)
        print(result?.val ?? "")