这是无量测试之道的第216篇原创
特别说明：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
解题思路：
一般二叉树相关的算法题，都可以使用递归这个编程技巧来解题，本题也不例外。
分析： 2个节点存在的位置，不外乎以下4种情况：
- 要么都在左子树上
- 要么都在右子树上
- 要么一个在左，一个在右
- 至少有一个不在这颗二叉树中【就是不在这个二叉树上的情况】
我们先看代码，然后来讲解解法，代码如下：
代码语言：javascript复制/**
* 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. 二叉树的前序遍历 如下图：一颗二叉数
前序遍历就是：先访问根节点、前序遍历左子树、前序遍历右子树。 过程如下:
- 先访问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
代码:
代码语言：javascript复制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. 然后前序遍历右子树
如果问你中序遍历【左根右】,你会写吗？
代码语言：javascript复制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
