LeetCode第236题二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 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。因为根据定义最近公共祖先节点可以为节点本身。

思路: LCA问题
      与二叉搜索树的最近公共祖先不同,此题左右节点大小没有固定关系.

　　　　　　　eg :    LCA(3,1) = 3　　//其中一个节点与3相等　 }
　　　　　　　　　　LCA(1,3) = 3　　//其中一个节点与3相等 　}
　　　　　　　　　　LCA(5,8) = 3　　//分部在3的左右子树中　 }   我们可以发现,只要  (一个在3的左边,一个在3的右边)||(其中一个节点的值与root相等)  ,LCA的值都为3
　　　　　　　　　　LCA(6,8) = 3　　//分布在3的左右子树　　 }　　
                                  LCA(8,7) = 3　　//分布在3的左右子树中　 }
　　　　　　　　　　LCA(6,4) = 5   　 //分布在5的左右子树中    }    当root为5时,与上一情况相同(一个在左一个在右)||(其中一个节点的值与root相同)
　　　　　　　　　　LCA(5,2) = 5　    //其中一个节点与5相等　}　
  　　　　　　　

      对搜索规则进行介绍:

 　　　　　　　目的:  以某个节点为根结点,如果两个问题节点分别在此根结点的左右两侧 或其中一个问题节点与这个节点相等,那么这个节点就是解.
　　　　　　　　　　　　　　　　　　　 如果两个问题节点都分布在根结点的一端,那么这个节点就不是解,但是这一端中包含着问题的解,而另一端则不含解

   　　　   　 1) 对于root节点: 如果root为空节点,返回null
                 　　　　   如果root与p或q相等,返回p或q. 

　　　　　　2) 如果没有在情况1返回,说明root不为空并且不与p,q相等
　　　　　　　　 那么,可能节点的分布存在以下情况:

　　　　　　　　 一:节点一个分布在root的左子树一个分布在root的右子树
　　　　　　　　 二:节点都分布在root的左子树
　　　　　　　　 三:节点都分布在root的右子树

　　　　　　　　 我们对左右节点分别进行递归.左右节点分别成为新root节点.(记为新root节点)
　　　　　　　　 
　　　　      3) 那么,左右两个搜索方法的返回值 searchLeft和searchRight 也根据搜索有了不同的情况
　　　　　　　　 一: searchLeft 和 searchRight 都不为空,对应着情况一
　　　　　　　　 二: searchLeft不为空,searchRight为空 , 对应着情况二
　　　　　　　　 三: searchRight不为空,searchLeft为空 , 对应着情况三

 1 class Solution236 {  2 
 3   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  4     if (root == null || root == p || root == q) {  5       return root;  6  }  7     TreeNode searchLeft = lowestCommonAncestor(root.left, p, q);  8     TreeNode searchRight = lowestCommonAncestor(root.right, p, q);  9 
10     if (searchLeft != null && searchRight != null) { //左右各有一个节点
11       return root; 12  } 13     if (searchLeft != null) { //节点都在左边
14       return searchLeft; 15  } 16     return searchRight; 17 
18  } 19 }