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

解法一：递归

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
236.二叉树的最近公共祖先 - 图1

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
236.二叉树的最近公共祖先 - 图2

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

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
解法一：递归
所有二叉树套路一样，先写框架：
```
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  left := lowestCommonAncestor(root.Left, p, q)
  right := lowestCommonAncestor(root.Right, p, q)
}
```
根据labuladong的理论：递归型问题需要考虑三个问题：

函数干嘛的？
函数参数中的变量（这里的变量不是传入的变量，是变化的那个的意思）是什么？
函数结果干什么用？

分别来解释下：

干嘛的？【定义】函数的作用是在输入 root、p、q 时，返回 p、q 的最近最近公共节点。若 root 是 p 和 q 的最近公共祖先，只有可能是以下情况之一：
1. p q 在 root 的子树中，且分列在 root 的异侧（分别在左右子树）
2. p q 只有一个在以 root 为根的树中，那么返回 root （实际上是 p 或者 q ）
3. p q 都不在以 root 为根的数中，那么显然是要返回 nil 的
变量是什么？【状态】变量是 root ，根据框架，函数肯定会递归调用 root.Left 和 root.Right ；至于 p、q 我们要找他们的公共祖先，所以他俩肯定不会变。可以把以 root 为根转移成以 root 的子节点为根作为【状态转移】
函数结果怎么用？观察问题的性质，找规律。变量是 root，所以我们要围绕 root 节点的情况来讨论。先来讨论递归的终止条件
1. root 为空，那显然是要返回 nil 了
2. root 本身就是 p 或 q ，那么就返回 root 即可

剩下的就是要分开讨论几种情况了，前面说的三种情况：

首先，如果p和q都在以root为根的树中，那么left和right一定分别是 p h和 q
如果p和q都不在以root为根的树中，直接返回null。
如果p和q只有一个存在于root为根的树中，函数返回该节点

这里为了保证 left 和 right 非空，分别是 p 和 q 时， root 一定是他们的最近公共祖先，所以使用的二叉树后序遍历。
前序遍历可以理解为从上往下，后续遍历可以理解为从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个 root 。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil {
        return root
    }
    if left == nil {
        return right
    }
    return right
}

看了下 K神的讲解，摘抄一下清晰的讲解：
递归解析：

终止条件：
1. 当越过叶节点，则直接返回 null ；
2. 当 root 等于 p, q ，则直接返回 root ；
递推工作：
1. 开启递归左子节点，返回值记为 left ；
2. 开启递归右子节点，返回值记为 right ；
返回值：根据 left和 right ，可展开为四种情况；
1. 当 left 和 right 同时为空：说明 root 的左 / 右子树中都不包含 p,q ，返回 null ；
2. 当 left 和 right 同时不为空：说明 p,q 分列在 root 的异侧（分别在左 / 右子树），因此 rootroot 为最近公共祖先，返回 root ；
3. 当 left 为空，rightright 不为空：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
  1. p,q 其中一个在 rootroot 的右子树中，此时 right 指向 pp（假设为 pp ）；
  2. p,q 两节点都在 root 的右子树中，此时的 right 指向最近公共祖先节点；
4. 当 left 不为空， right 为空：与情况 3. 同理；

解法一：递归