# LeetCode-236-二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例1：
代码语言：javascript复制输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例2：
代码语言：javascript复制输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
# 解题思路
方法1、递归：
参考链接https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
根据上述示例可以得知，如果root是p，q的最近公共祖先，则可能的情况有以下3种：
- root节点的子树包含p和q两个节点，且p和q分别在root的左、右子树中；
- p=root，且q在root的左/右子树中；
- q=root，且p在root的左/右子树中；
递归解析：
1、终止条件：
- 当越过叶节点，则直接返回null；
- 当root等于p,q，则直接返回root；
2、递推工作：
- 开启递归左子节点，返回值记为left；
- 开启递归右子节点，返回值记为right；
**3、返回值：**根据left和right，可展开为四种情况；
- 当left和right同时为空：说明root的左/右子树中都不包含p,q，返回null；
- 当left和right同时不为空：说明p,q分列在root的左/右子树，因此root为最近公共祖先，返回root；
- 当left为空，right不为空：p,q都不在root的左子树中，直接返回right。具体可分为两种情况：
- p,q其中一个在root的右子树中，此时right指向p(假设为p)；
- p,q两节点都在root的右子树中，此时right指向最近公共祖先节点；
- 当left不为空，right为空：与情况3同理；
观察发现，情况1可合并至3和4内
# Java代码1
代码语言：javascript复制/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||root==p||root==q) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left==null) return right;
if(right==null) return left;
return root;
}
}
# Java代码2
代码语言：javascript复制class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) return null; // 1.
if(left == null) return right; // 3.
if(right == null) return left; // 4.
return root; // 2. if(left != null and right != null)
}
}
# Java代码3
逻辑更清晰版本，出处https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/comments/
代码语言：javascript复制public class Solution {//所有的递归的返回值有4种可能性，null、p、q、公共祖先
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {//当遍历到叶结点后就会返回null
return root;
}
if (root == p || root == q) {//当找到p或者q的是时候就会返回pq
return root;/*当然，值得一提的是，如果公共祖先是自己（pq），并不需要寻找另外
一个，我们在执行前序遍历会先找上面的，后找下面的，我们会直接返回公共祖先。*/
}
TreeNode left = LowestCommonAncestor(root.left, p, q);//返回的结点进行保存，可能是null
TreeNode right = LowestCommonAncestor(root.right, p, q);//也可能是pq，还可能是公共祖先
if (left != null && right != null) {
return root;//如果左右都存在，就说明pq都出现了，这就是，公共祖先，此时不用考虑公共祖先是自己的情况，因为上面已经做过判断了。
} else if (left != null) {//否则我们返回已经找到的那个值（存储在left，与right中），p或者q
return left;//还有一种可能就是，由下面返回的公共祖先，并将这个值一路返回到最表层
} else if (right != null) {
return right;
}
return null;
}
}
