劍指offer計劃19（ 搜索與回溯演算法中等）—java

• 2021 年 9 月 19 日
• 筆記
• 面試和leetcode技巧

1.1、題目1

劍指 Offer 64. 求1+2+…+n

1.2、解法

這題看評論區真的絕了，都是人才，各個說話都好聽，我看到個還有用異常來結束的就離譜。
這題用了&&當左邊為false,右邊不執行的原理。

1.3、程式碼

class Solution {
    public int sumNums(int n) {
       boolean flag = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

2.1、題目2

劍指 Offer 68 – I. 二叉搜索樹的最近公共祖先

2.2、解法

因為是二叉搜索樹，所以當前值大於兩個值時，應該往左子樹找，
當前值小於兩個值時，應該往右子樹找。

2.3、程式碼

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

3.1、題目3

劍指 Offer 68 – II. 二叉樹的最近公共祖先

3.2、解法

開頭判斷是否是相同或者空的情況，然後設兩個結點來遍歷兩邊的字數，如果左邊為空，則返回右邊，
反之，則返回左邊，兩者都不滿足，則返回root。

3.3、程式碼

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

}