需求
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
思路
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢？
回溯啊，二叉树回溯的过程就是从低到上。
后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。
首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。 即情况一：
判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。
那么有录友可能疑惑，会不会左子树 遇到q 返回，右子树也遇到q返回，这样并没有找到 q 和p的最近祖先。
这么想的录友，要审题了，题目强调：二叉树节点数值是不重复的，而且一定存在 q 和 p。
但是很多人容易忽略一个情况，就是节点本身p(q)，它拥有一个子孙节点q(p)。 情况二：
在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
那么为什么要遍历整棵树呢？直观上来看，找到最近公共祖先，直接一路返回就可以了。
就像图中一样直接返回7。
但事实上还要遍历根节点右子树（即使此时已经找到了目标节点了），也就是图中的节点4、15、20。
因为在如下代码的后序遍历中，如果想利用left和right做逻辑处理， 不能立刻返回，而是要等left与right逻辑处理完之后才能返回。
left = 递归函数(root->left); // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理; // 中
所以此时大家要知道我们要遍历整棵树。知道这一点，对本题就有一定深度的理解了。
那么先用left和right接住左子树和右子树的返回值，代码如下：
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解
如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。
这里有的同学就理解不了了，为什么left为空，right不为空，目标节点通过right返回呢？
如图：
图中节点10的左子树返回null，右子树返回目标值7，那么此时节点10的处理逻辑就是把右子树的返回值（最近公共祖先7）返回上去！
这里也很重要，可能刷过这道题目的同学，都不清楚结果究竟是如何从底层一层一层传到头结点的。
那么如果left和right都为空，则返回left或者right都是可以的，也就是返回空。
代码如下：
if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else { // (left == NULL && right == NULL)
return NULL;
}
那么寻找最小公共祖先，完整流程图如下：
/**
* 236. 二叉树的最近公共祖先
* 公共祖先需要由下往上反值所以
* 使用后续遍历，左右中的方式将值返回到根节点得到结果
*/
public class LowestCommonAncestor236 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 开始传入root 为null，或者遍历到叶子节点
if(root == null) return null;
// 叶子节点为P 或者 Q
if(root.val == p.val || root.val == q.val) return root;
// 左
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 右
TreeNode right = lowestCommonAncestor(root.right, p , q);
// 中
// 代表找到了公共祖先向上反
if(left !=null && right!=null){ return root;
}
// 代表找到了P 或者Q
if(left ==null && right !=null){return right;
}else if(left !=null && right ==null){
//代表找打了P 或者Q
return left;
}else {
// 未找到P 或者 Q
return null;
}
}
}
