最近公共祖先的定义： 设节点 rootroot 为节点 p, qp,q 的某公共祖先，若其左子节点 root.leftroot.left 和右子节点 root.rightroot.right 都不是 p,qp,q 的公共祖先，则称 rootroot 是 “最近的公共祖先” 。
根据以上定义，若 rootroot 是 p, qp,q 的 最近公共祖先 ，则只可能为以下情况之一：
pp 和 qq 在 rootroot 的子树中，且分列 rootroot 的 异侧（即分别在左、右子树中）；
p = rootp=root ，且 qq 在 rootroot 的左或右子树中；
q = rootq=root ，且 pp 在 rootroot 的左或右子树中；
作者：jyd
链接：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/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法1：深度优先搜索+递归
思路：
(1) 递归搜索二叉树，找到 p 和 q 的最近公共父节点。
(2) 如果 p 和 q 分别位于原二叉树的左右分支，则直接返回根节点。
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)
}
}
方法二：利用对根节点左子树进行中序遍历，找p,q是不是都在左子树，如果都在，对根节点左子节点递归，如果一个在一个不在，返回root
class Solution {//方法一：上一题二叉搜索树里是通过比较数值来知道现在在哪个子树，现在只能靠其他方式
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
boolean pLeft=false;
boolean qLeft=false;//这俩变量，标识p,q在不在左子树
if(root==null||root==p||root==q)
{
return root;
}
Stack<TreeNode> stack=new Stack<>();
TreeNode cur=root.left;//对左子树做遍历，找左子树里面有没有p,q
while(cur!=null||!stack.isEmpty())
{
while(cur!=null)//先将左子节点入栈，直到为空
{
stack.push(cur);
cur=cur.left;
}
cur=stack.pop();
if(cur.val==p.val)
{
pLeft=true;
}
if(cur.val==q.val)
{
qLeft=true;
}
if(pLeft&&qLeft)
{
break;
}
cur=cur.right;
}
if(pLeft&&qLeft) return lowestCommonAncestor(root.left,p,q);
if(qLeft||pLeft) return root;//一个在左子树，一个右子树，此时说明最近公共祖先是根节点
return lowestCommonAncestor(root.right,p,q);
}
}