二叉树最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉树中。

解题思路：
通过上述对公共祖先的解释，其实我们可以发现对于一个节点而言，如果这个点是p，q的最近公共祖先节点，我们大致可以分成三种情况：
1.p，q在root的子树中，那么p，q一定在root的右侧
2.p为root，且q在p的子树中
3.q为root，且p在q的子树中
我们通过后序遍历，从最深处向上遍历
递归解析：
1.首先结束条件：如果越过了p，q就返回null，如果root等于p，q那就返回p，q
2.递推工作：开启递归左子节点，返回值为left，开启递归右子节点，返回值为right
3.根据left和right的返回情况我们可以分成以下几点
·当left和right同时为空，说明p，q不在root的子树中，直接返回null
·当left和right同时不为空时，说明p，q在root的异侧，那么root就是p，q的最近公共祖先节点，所以返回root
·当left为空，right不为空时，说明此时，pq都不在root的左子树中，则直接返回root，此时可能有两种情况：p，q有一个在right中，那么我们返回的right指向p或q；p，q都在right中那么我们返回的就是最近公共父节点
·当right为空，left不为空时同上
我们通过图解来更好的理解这个含义
例一：找到7和8的最近公共祖先节点

例二：找到2和4的最近公共祖先节点

具体的代码实现：

public static TreeNode1 lowestCommonAncestor(TreeNode1 root, TreeNode1 p, TreeNode1 q) {
	      if(root == null||root == p || root ==q) {
	    	  return root;
	      }
	      TreeNode1 left = lowestCommonAncestor(root.left, p, q);
	      TreeNode1 right = lowestCommonAncestor(root.right, p, q);
	      if(left == null && right == null) return null;
	        if(left == null) return right; 
	        if(right == null) return left; 
	        return root; //当左右都不为空时
	  }