Leetcode236经典题目二叉树的最近公共祖先
本次为大家带来的题目是leetcode236二叉树的最近公共祖先
本道题的直观思路是自底向上进行寻找，如果存在的话那么向上返回，如何能够自底向上遍历呢？我们可以利用回溯进行处理，那么需要注意的是进行回溯的时候一定要使用后序遍历来操作，因为后序遍历的顺序是左、右、根，那么在根节点也就是我们进行判断的操作了。
下面说下可能存在的情况
1.如果当前节点的左和右子树都不为空，那么说明找到了公共祖先，直接返回。
2.假如节点左子树为空，右子树不为空，说明我们要继续向上返回。同理右子树为空左子树不为空也要返回。
具体的代码实现如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//终止条件
if(root==null) return null;
//如果当前节点为q或p直接返回
if(root==p||root==q) return root;
//后序遍历
//左
TreeNode left = lowestCommonAncestor(root.left,p,q);
//右
TreeNode right = lowestCommonAncestor(root.right,p,q);
//根
//左右都不为空，说明存在q，p
if(left!=null&&right!=null){
return root;
}else if(left!=null &&right==null){
return left;
}else if(right!=null&&left==null){
return right;
}else{
return null;
}
}
}