摘要：題目意思就是要一個(gè)個(gè)的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。然后將兩個(gè)不正確的點(diǎn)記錄下來，最后回原來正確的值。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹。思想來自于的代碼實(shí)現(xiàn)。

跳過總結(jié)請(qǐng)點(diǎn)這里：
https://segmentfault.com/a/11...

BST最明顯的特點(diǎn)就是root.left.val < root.val < root.right.val.
還有另一個(gè)特點(diǎn)就是，bst inorder traversal result is an ascending array.

下面簡單表示一個(gè)BST:

             60
         /        
        40         80
      /          /  
     20     50   70   90
    /                 
  10   30              100

BST inorder traversal result is: 10 20 30 40 50 60 70 80 90 100.

BST 和普通的樹的區(qū)別就在于它是一個(gè)有序的，為了保證順序，我們需要通過inorder traversal得到，所以幾乎所有l(wèi)eetcode關(guān)于bst的題目，都是在考我們?nèi)绾卫胕norder traverse.

簡單題目只過代碼思路，代碼會(huì)附在題號(hào)底下，為了減少博客篇幅，題目描述細(xì)節(jié)請(qǐng)參看leetcode。

LC 173 Binary Search Tree Iterator.
Calling next() will return the next smallest number in the BST.

題目意思就是要一個(gè)個(gè)的返回bst當(dāng)前的最小值。強(qiáng)提示：有序。
所以解法自然就是bst inorder traverse。起點(diǎn)就是BST里最小的值，也就是leftmost.

public class BSTIterator {
    ArrayDeque stk;
    
    public BSTIterator(TreeNode root) {
        stk = new ArrayDeque();
        pushAll(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stk.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stk.pop();
        if(node.right !=null) {
            pushAll(node.right);
        }
        return node.val;
    }
    
    public void pushAll(TreeNode node){
        while(node != null){
            stk.push(node);
            node = node.left;
        }
    }
}

新增了預(yù)處理的方法。這個(gè)方法的好處就是每次next()都是嚴(yán)格的O(1), 而上面那個(gè)方法只是AVE O(1).

public class BSTIterator {
    ArrayList ascending;
    int pos = 0;
    
    public BSTIterator(TreeNode root) {
        ascending = new ArrayList();
        inorder(root, ascending);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return pos < ascending.size();
    }

    /** @return the next smallest number */
    public int next() {
        return ascending.get(pos++);
    }
    
    public void inorder(TreeNode root, ArrayList ascending){
        if(root == null) return;
        inorder(root.left, ascending);
        ascending.add(root.val);
        inorder(root.right, ascending);
    }
}

LC 230 Kth Smallest Element in a BST

返回BST里第k小的元素。 強(qiáng)提示：有序。
從leftmost開始，找到第k個(gè)點(diǎn)返回。時(shí)間復(fù)雜度近似到O(K).
為了寫代碼的清晰度，我們使用recursion的方法做inorder traversal。

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        if(root == null) return 0;
        int[] res = {Integer.MIN_VALUE};
        kthSmallest(root, k, res);
        return res[0];
    }
    
    public int kthSmallest(TreeNode root, int k, int[] res){
        if(res[0] != Integer.MIN_VALUE || root == null){    //if finded kth, all recursion will immediately return to root.
            return 0;
        }
        int left = kthSmallest(root.left, k,res);
        if(left == k-1){
            res[0] = root.val;
        }
        int right = kthSmallest(root.right, k - left -1, res);
        return left + right + 1;
  

LC99 Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.

如果BST中有兩個(gè)節(jié)點(diǎn)位置互相交換了，怎么辦？ 表明BST的順序被打亂。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。

利用上面給的BST的圖，我們swap(20, 90)，得到如下BST：

             60
         /        
        40         80
      /          /  
     90     50   70   20
    /                 
  10   30              100

inorder traversal result is:
10 90 30 40 50 60 70 80 20 100
this is not an ascending array.
90 >30, 80 >20 這兩處順序不合理，靠前的值大于靠后的值。
所以這里我們?cè)趇norder traversal的同時(shí)，我們還需要比較pre.val和cur.val。
然后將兩個(gè)不正確的點(diǎn)記錄下來，最后swap回原來正確的值。

public class Solution {
    private TreeNode firstNode = null;
    private TreeNode secondNode = null;
    private TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
    
    public void recoverTree(TreeNode root) {
        if(root == null) return;
        inorderTraversal(root);
        
        int temp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = temp;
    }
    
    public void inorderTraversal(TreeNode root){
        if(root == null) return;
        
        inorderTraversal(root.left);
        
        if(firstNode == null && preNode.val > root.val) {
            firstNode = preNode;
        }
        
        if(firstNode != null && preNode.val > root.val) {
            secondNode = root;
        }
        
        preNode = root;
        
        inorderTraversal(root.right);
        
    }
}

LC450 Delete Node in a BST

找到一個(gè)點(diǎn)容易，利用root.left.val < root.val < root.right.val，時(shí)間復(fù)雜度O（logN)找到。
刪除一個(gè)點(diǎn)。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹。都容易操作。
如果是中間節(jié)點(diǎn)怎么辦？我們找到它在bst里的前一個(gè)點(diǎn)（或者后一個(gè)點(diǎn)），改變要?jiǎng)h除節(jié)點(diǎn)的值，然后刪除它的前一個(gè)點(diǎn)。
思想來自于heap的代碼實(shí)現(xiàn)。我們每次Pop的時(shí)候取的是根節(jié)點(diǎn)的值，然后把heap里最尾端的點(diǎn)換到根節(jié)點(diǎn)，然后shift down。

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        
        if(key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if(key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if(root.left == null) {
                return root.right;
            } else if(root.right == null) {
                return root.left;
            }
            
            TreeNode node = findNextMin(root.right);
            root.val = node.val;
            root.right = deleteNode(root.right, node.val);
        }
        return root;
    }
    
    public TreeNode findNextMin(TreeNode node) {
        while(node.left != null) {
            node = node.left;
        }
        return node;
    }
}  

寫不下了，換一篇，點(diǎn)這里：
https://segmentfault.com/a/11...