問題1

平衡二叉樹的公共祖先，找到該樹中兩個指定節(jié)點的最近公共祖先

原理

• 首先需要了解平衡二叉樹的特性，平衡二叉樹的左子樹的節(jié)點值小于根節(jié)點的值，平衡二叉樹的右子樹的節(jié)點值大于根節(jié)點。
• 判斷p,q和root的關系，如果root>p&&root>q說明應該遞歸遍歷左子樹；如果p<root&&q<root 說明應該遞歸遍歷右子樹，否則就是當前root節(jié)點。

代碼

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root.val>p.val&&root.val>q.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val<p.val&&root.val<q.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }
}

注意事項

• root<p&&root<q 和root>p&&root>q 這兩個都是且的關系

問題2

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

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

原理

• 遞歸找左子樹，遞歸找右子樹
• 左子樹為空，返回右子樹；右子樹為空返回左子樹；左右子樹都不為空，返回當前節(jié)點
• 遞歸的終止條件，當前節(jié)點為空，或者當前節(jié)點等于p或者當前節(jié)點等于q

代碼

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?right:left;
    }
}

注意事項

• 遞歸的終止條件：當前節(jié)點為空，或者當前節(jié)點等于p或者當前節(jié)點等于q