题目大意：
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点5和节点1的最近公共祖先是节点3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点5和节点4的最近公共祖先是节点5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=236
解题思路：
本题我用了2种解题方法，执行时间仅相差1ms，第一种略优于第二种，且代码量少，不过有些难于理解。而第二种虽然代码量多，但是思路非常简单，便于记忆。
先来看第一种递归思路。我们知道，如果节点p和q分别位于某个节点的左右两颗子树中，那么该节点就是返回结果。因此我们的主要目标就是从root开始查看p和q是否分别位于其左右两侧，如果不是，说明他们同时存在于root的某一侧之中，然后再以这一侧作为root，继续执行同样的逻辑。
那么如何判断p和q的位置？这里就需要用到递归，递归的根本目的是在子树中深度寻找p和q，看其是否在该子树中。递归开始，root逐层向下，当root等于p或者q时，说明找到了其中之一，开始向递归上层返回，并在上层的另一侧寻找另一个目标，如果找到，当前节点即是返回结果，如果没有则继续向上返回，直到找到为止。如果还没看懂，可以参考一下代码，代码中有详细注释。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// root若为空，还找个毛线，直接返回空（返回空的root本身即可）
// root若等于p或者q，说明找到了其中一个元素，返回递归上一层。(*1)
if (root == null || root == p || root == q) {
return root;
}
// 如果当前层还没找到p或者q（root不等于p或者q），继续向下层寻找
// 这里递归的顺序是先左侧深度遍历，再右侧。
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 如果左右两侧分别不为空，说明当前root下，p和q分别位于其左右，root即返回结果。(*2)
// 这里解释下为什么是null判断，因为我们所有递归返回的结果要么空，要么是p或q
// 因此，只要不是空，那么必定是p和q其中之一，为了便于理解，也可写成：
// if (left == p && right == q || left == q && right == p)
if (left != null && right != null) {
return root;
}
// 如果左右两边都为空，那么不论返回左还是右，返回的都是空。
// 如果左右两边其中之一不为空，那么返回那个不为空的值，这个不为空的值有2种可能
// 其一是找到的p或者q，上面代码标注(*1)的返回值（与现在比更深层的递归返回值）。
// 其二是找到的q或者q的共同父节点。上面代码标注(*2)的返回值（与现在比更深层的递归返回值）。
// 第二种可能是找到了最终结果，所以当递归向上层返回时，可以保证左右两侧只有一个不为空
// 因此，结果可以保证返回到最上层。
return left == null ? right : left;
}本解法用时5ms。
如果看了上面的分析和代码还是没搞懂，那么我们来看下一个非常简单的思路。这道题是要找任意两个节点的共同父节点，我们可以想一下，二叉树中每个节点有两个子节点，但父节点只有一个，也就是说，从p和q向二叉树上方走，他们分别只有一条路径能到达顶部root，所以在他们向上的2条路径发生相交时的节点即是结果。写代码时，我们可以从p和q出发，将他们每一个父节点记录到一个List中，当父节点第二次出现时，说明此时两条路径相交，该节点即是返回结果。这样做是不是很简单？！
但是问题来了，题目给出的TreeNode类中，并没有父节点信息，因此，我们需要做一步反向建模，将每个节点的父节点先找到，找到之后问题就会迎刃而解。思路比较清晰，我们直接看代码，代码中也有详细注释。
// 为了得到每个节点的父节点，我们自己定义一个类。
public class MyTreeNode {
MyTreeNode(TreeNode node, MyTreeNode topNode) {
treeNode = node;
top = topNode;
}
MyTreeNode top; // 记录父节点
TreeNode treeNode; // 记录当前节点
}
int valP, valQ; // 分别记录p和q的值
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
valP = p.val;
valQ = q.val;
// 将root包装一下，记录下每个子节点的父节点。
helper(root, null);
// 定义一个用于保存p和q所以父节点用的List
List<Integer> list = new ArrayList<>();
// 因为p和q本身也可以作为父节点，先将其值存入list中。
list.add(valP);
list.add(valQ);
// 开始遍历p和q的所有父节点。
while (mp.top != null || mq.top != null) {
if (mp.top != null) {
// 如果list中已存在当前p的父节点，那么该父节点即是返回值
if (list.contains(mp.top.treeNode.val)) {
return mp.top.treeNode;
}
// 若list中不存在，将此父节点值存入list
list.add(mp.top.treeNode.val);
// 将p节点设为其父节点，为了下一次遍历
mp = mp.top;
}
if (mq.top != null) {
// 同理，如果list中已存在当前q的父节点，那么该父节点即是返回值
if (list.contains(mq.top.treeNode.val)) {
return mq.top.treeNode;
}
list.add(mq.top.treeNode.val);
mq = mq.top;
}
}
return null;
}
MyTreeNode mp, mq; // 记录包装好的p和q节点
// 该方法用于为每个节点记录其父节点
// 因为是找p和q的父节点，因此p和q以下的节点都不需要包装了
private void helper(TreeNode current, MyTreeNode root) {
// 如果当前节点为空或者p和q均已包装好，可以结束此方法
if (current == null || mp != null && mq != null) {
return;
}
// 新建一个包装类MyTreeNode
MyTreeNode myTreeNode = new MyTreeNode(current, root);
// 如果当前节点为p，则将包装好的p保存到全局变量中
if (current.val == valP) {
mp = myTreeNode;
}
// 如果当前节点为q，则将包装好的p保存到全局变量中
if (current.val == valQ) {
mq = myTreeNode;
}
// 继续为该节点的左右子节点包装，左右子节点的父节点为当前节点。
helper(current.left, myTreeNode);
helper(current.right, myTreeNode);
}本解法用时6ms，略微逊色于第一种解法。
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/236-lowest-common-ancestor-of-a-binary-tree-解题思路分析/