【leetcode-樹】二叉樹的最近公共祖先
題目：
給定一個二叉樹, 找到該樹中兩個指定節(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é)點且均存在于給定的二叉樹中米同。
思路：
后序遍歷二叉樹 假設(shè)遍歷到的當前結(jié)點為cur 先處理左子樹和右子樹 left和right
如果cur為null 或者為p和q中的任意一個, 直接返回cur
如果left和right都不為null， 說明p摔竿，q在cur的兩側(cè)面粮， 返回cur
如果left不為null， 說明在left側(cè)找到了p或q, 返回left,繼續(xù)遞歸遍歷left側(cè)
如果right不為null 說明在right側(cè)找到了p或q, 返回right,繼續(xù)遞歸遍歷right側(cè)
java代碼：
/**
* 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 || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left !=null && right!=null) {
return root;
}
return left != null ? left : right;
}
}
