530.Minimum Absolute Difference in BST 二叉搜尋樹中的最小差的絕對值

［抄題］：

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
      

 [暴力解法]：

時間分析：

空間分析：

［奇葩輸出條件］：

［奇葩corner case］：

［思維問題］：

基礎弱到忘了二叉樹的traverse怎麼寫了，還以為要輸出到array

［一句話思路］：

先初始化為MAX_VALUE，再按标準格式寫

［輸入量］：空： 正常情況：特大：特小：程式裡處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫圖］：

［一刷］：

1. traverse函數裡面切勿定義變量，會導緻重複指派出錯。以前錯了沒注意
2. 四則運算的對象也要滿足非空not null 的基本條件

［二刷］：

［三刷］：

［四刷］：

［五刷］：

  [五分鐘肉眼debug的結果]：

［總結］：

先初始化為MAX_VALUE，再按标準格式寫

［複雜度］：Time complexity: O(n

［英文資料結構或算法，為什麼不用别的資料結構或算法］：

［關鍵模闆化代碼］：

左中右

getMinimumDifference(root.left);
        
        if (prev != null) {
            min = Math.min(min, root.val - prev);
        }
        prev = root.val;
        
        getMinimumDifference(root.right);      

［其他解法］：

［Follow Up］：

 不是BST，用treeset，複雜度都是lgn，可以取出任何一個元素

［LC給出的題目變變變］：

 [代碼風格] ：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int min = Integer.MAX_VALUE;
    TreeNode prev = null;
    
    public int getMinimumDifference(TreeNode root) {
        //corner case
        if (root == null) {
            return min;
        }
        //in-order traversal
        getMinimumDifference(root.left);
        if (prev != null) {//only deletable if not null
            min = Math.min(min, root.val - prev.val);
        }
        //refresh the prev
        prev = root;
        getMinimumDifference(root.right);
        //return
        return min;
    }
}      

View Code

轉載于:https://www.cnblogs.com/immiao0319/p/8565405.html