LeetCode 236：二叉树的最近公共祖先

这是无量测试之道的第216篇原创

特别说明：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

解题思路：

  一般二叉树相关的算法题，都可以使用递归这个编程技巧来解题，本题也不例外。

分析： 2个节点存在的位置，不外乎以下4种情况：

1. 要么都在左子树上
2. 要么都在右子树上
3. 要么一个在左，一个在右
4. 至少有一个不在这颗二叉树中【就是不在这个二叉树上的情况】

我们先看代码，然后来讲解解法，代码如下：

/**
 * 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? {
        if root == nil || root?.val == p?.val || root?.val == q?.val { return root }
        let left = lowestCommonAncestor(root?.left, p, q)
        let right = lowestCommonAncestor(root?.right, p, q)
        if left != nil && right != nil { return root }
        return left == nil ? right : left
    }
}

代码解析： 先是边界条件的判断    1. if root为nil，直接 return    2. if root.val == q.val 或者 root.val == p.val，直接 return

下面是递归逻辑：    1. 先从左子树上找共同的祖先，记为left    2. 再从右子树上找共同的祖先，记为right

   如果left和right都不为nil，说明满足上述的条件3【一个在左，一个在右】，所以很显然，祖先节点就是根节点root；

   如果left不为nil，则返回left，否则返回right。这里面就包含了剩下3种条件，left不为nil，说明2个节点都在左子树上。如果left为nil，则说明要么2个节点都在右子树上，或者至少有一个不在这个二叉树上。

关于递归：

   递归这种编程技巧是非常有用的，掌握它，可以为我们解决很多思考起来很麻烦的题目。为了更好的理解递归，大家可以看我之前写的文章：leetcode 递归编程技巧-链表算法题。为了让大家体会到递归的强大，我们再看1道题： LeetCode 144. 二叉树的前序遍历 如下图：一颗二叉数

前序遍历就是：先访问根节点、前序遍历左子树、前序遍历右子树。 过程如下:

1. 先访问5，然后使用中序遍历去访问 5.left，再然后使用前序遍历去访问 5.right。 1.1. 中序遍历去访问5.left 先访问3，然后使用中序遍历去访问 3.left，再然后使用前序遍历去访问 3.right。 ... ... 1.2. 中序遍历去访问5.right 先访问7，然后使用中序遍历去访问 7.left，再然后使用前序遍历去访问 7.right。 ... ...

打印结果就是：5-3-1-0-2-4-7-6-8-9

代码:

class Solution {
    var nums = [Int]()
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
            nums.append(root.val)
            inorderTraversal(root.left)
            inorderTraversal(root.right)
    return nums
        }
}

代码解析： 先是边界条件的判断    1. 先访问根节点    2. 然后前序遍历左子树    2. 然后前序遍历右子树

如果问你中序遍历【左根右】,你会写吗？

class Solution {
    var nums = [Int]()
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
            inorderTraversal(root.left)
            nums.append(root.val)
            inorderTraversal(root.right)
    return nums
        }
}

  对，你没看错。就是这么简单，把它的访问放在中间就是【以后写一些算法的时候，可以把逻辑写在中间】。那么后序遍历了?一样，把访问 nums.append(root.val) 代码放在最后一行就是了。这就是递归的魅力。

总结：

  今天主要讲了一道leetcode上面的第236道算法题，其核心思想就是使用递归来实现的。后续为了让大家体会到递归编程技巧的强大，我又借二叉树的遍历例子用递归来实现为大家展示递归的强大。大家如果想更好的理解递归的调用栈的话，可以看我自己写的文章：leetcode 递归编程技巧-链表算法题。希望能帮助到大家。

end