題目:
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為:“對于有根樹 T 的兩個節點 p、q,最近公共祖先表示為一個節點 x,滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個節點也可以是它自己的祖先)。”
示例 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 。因為根據定義最近公共祖先節點可以為節點本身。
示例 3:
輸入:root = [1,2], p = 1, q = 2
輸出:1
class Solution {
private TreeNode ans;
public Solution() {
this.ans = null;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}