給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”

例如，給定如下二叉樹:??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é)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。
示例?2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。
?

說明:

所有節(jié)點的值都是唯一的。
p、q 為不同節(jié)點且均存在于給定的二叉樹中。

代碼：

/**

?*?Definition?for?a?binary?tree?node.

?*?public?class?TreeNode?{

?*?????int?val;

?*?????TreeNode?left;

?*?????TreeNode?right;

?*?????TreeNode(int?x)?{?val?=?x;?}

?*?}

?*/

class?Solution?{

????public?TreeNode?lowestCommonAncestor(TreeNode?root,?TreeNode?p,?TreeNode?q)?{

????????if(root==null){//遍歷到葉節(jié)點，還沒找到p，q，說明這條路徑不存在p，q，也就不存在祖先

????????????return?null;

????????}

????????if(root==p||root==q){//如果p或q等于root，說明找到了p或者q，返回他的值

????????????return?root;

????????}

????????TreeNode?left?=?lowestCommonAncestor(root.left,p,q);

????????TreeNode?right?=?lowestCommonAncestor(root.right,p,q);

????????if(left!=null&&right!=null){//root的左右分別是p，q，那么root就是祖先

????????????return?root;

????????}else?if(left!=null){//root的右邊沒找到pq，那么左邊就是祖先結(jié)點

????????????return?left;

????????}else?if(right!=null){//...

????????????return?right;

????????}

????????return?null;//如果左右都為空，那么一定是null，不存在要找的結(jié)點

????}

}

?

?

?

tips：雖然ac了，但是自己找案例還是有一些bug，比如在題上給的案例中尋找5，10兩個結(jié)點，一個存在于這個二叉樹，而另一個結(jié)點不存在，仍然返回5，而不是null

總結(jié)

以上是生活随笔為你收集整理的Leetcode--236. 二叉树的最近公共祖先（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。