題目描述：
給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先诫肠。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p躁锡、q煤伟，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x瞭吃，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）杜跷“睿”
例如，給定如下二叉樹: 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
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3葛闷。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5憋槐。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
解法：
遞歸法
因?yàn)閘owestCommonAncestor(root,p,q)的功能是找出以root為根節(jié)點(diǎn)的兩個(gè)節(jié)點(diǎn)p和q的最近公共祖先淑趾，所以遞歸體分三種情況討論：
1.如果p和q分別是root的左右節(jié)點(diǎn)阳仔，那么root就是我們要找的最近公共祖先
2.如果p和q都是root的左節(jié)點(diǎn)，那么返回lowestCommonAncestor(root.left,p,q)
3.如果p和q都是root的右節(jié)點(diǎn)扣泊，那么返回lowestCommonAncestor(root.right,p,q)
邊界情況討論：
1.如果root是null近范，說明我們已經(jīng)找到最底了，返回null
2.如果root與p或q相等旷赖，則返回root
3.如果左子樹沒找到顺又，遞歸函數(shù)返回null，證明p,q同在root的右側(cè)等孵，那么最終的公共祖先就是右子樹找到的節(jié)點(diǎn)
4.如果右子樹沒找到，遞歸函數(shù)返回null蹂空，證明p,q同在root的左側(cè)俯萌，那么最終的公共祖先就是左子樹找到的節(jié)點(diǎn)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//判斷邊界情況
if(root==null || p==root || q==root ){
return root;
}
//遞歸查找左子樹
TreeNode left = lowestCommonAncestor(root.left,p,q);
//遞歸查找右子樹
TreeNode right = lowestCommonAncestor(root.right,p,q);
//若左子樹查詢結(jié)果為空，則返回右子樹查詢結(jié)果
if(left==null) return right;
//若右子樹查詢結(jié)果為空上枕，則返回左子樹查詢結(jié)果
if(right==null) return left;
//否則返回root
return root;
}
}
