# BST

* **递归时，要考虑状态可能的不连续性。**
* **取左右子树的 min/max 之后加上当前节点是最常见的递归结构，保证了 path 自顶向下的连续。**
* **BST 做 in order traversal 得到的结果是 sorted.**
* **BST 中 root 的左子树所有点小于 root; 右子树所有点大于 root.**
* **一个正确的 BST 中每一个点都有其合理的取值闭区间，为【左子树 max , 右子树 min】，最左右两端的点为一端开放区间。**
* **维护大小为 k 的 MaxHeap:**

```java
PriorityQueue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());
```

### Tree 类问题中，递归转迭代的常用手法，就是利用尾递归。

### [Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value/)

#### 所谓 “最近的点”，可能是 parent ，可能是 child，可能在左边，也可能在右边。

* **所以一要存好 prev;**
* **二要两边都探，不能沿着一边硬走。**

```java
public class Solution {
    public int closestValue(TreeNode root, double target) {
        return find(root, target, null);
    }

    public int find(TreeNode root, double target, Integer prev){
        if(root == null) return -1; // Error
        if(prev == null) prev = root.val;

        prev = (Math.abs(root.val - target) < Math.abs(prev - target)) ? root.val: prev;

        if(root.left != null && target < root.val){
            return find(root.left, target, prev);
        }
        if(root.right != null && target > root.val){
            return find(root.right, target, prev);
        }

        return prev;
    }
}
```

#### 这题论坛里还有更简洁直接的迭代写法，其实就是尾递归变迭代；

```java
public int closestValue(TreeNode root, double target) {
    int ret = root.val;   
    while(root != null){
        if(Math.abs(target - root.val) < Math.abs(target - ret)){
            ret = root.val;
        }      
        root = root.val > target? root.left: root.right;
    }     
    return ret;
}
```

### [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)

一开始写挂了两次，因为忘了另外的条件，就是右子树里面的最小值一定要大于 root，并且左子树里面的最大值一定要小于 root 才行。

* **多研究下 subtree 的结构和性质，目前对这个理解还不够。**
* **递归时，要考虑状态可能的不连续性，这题和** [**Binary Tree Maximum Path Sum**](https://leetcode.com/problems/binary-tree-maximum-path-sum/) **很像。**

写的比较粗糙的第一版，用 Tuple 存非连续子树信息；

```java
public class Solution {
    private class Tuple{
        boolean isValid;
        TreeNode min;
        TreeNode max;
        public Tuple(boolean isValid, TreeNode min, TreeNode max){
            this.isValid = isValid;
            this.min = min;
            this.max = max;
        }
    }    

    public boolean isValidBST(TreeNode root) {
        return helper(root).isValid;
    }

    private Tuple helper(TreeNode root){
        if(root == null) return new Tuple(true, null, null);

        Tuple left = helper(root.left);
        Tuple right = helper(root.right);

        if(!left.isValid || !right.isValid) return new Tuple(false, null, null);

        if(left.max != null && root.val <= left.max.val) return new Tuple(false, null, null);
        if(right.min != null && root.val >= right.min.val) return new Tuple(false, null, null);

        TreeNode min = null;
        TreeNode max = null;
        if(left.min == null){
            min = root;
        } else {
            min = (root.val < left.min.val) ? root : left.min;
        }

        if(right.max == null){
            max = root;
        } else {
            max = (root.val > right.max.val) ? root : right.max;
        }

        return new Tuple(true, min, max);
    }
}
```

顺着这个思路，更简洁清晰的写法是这样。

* **这个写法是在 BST 中定义 “区间”，即对于一个正在考虑的 root，检查值是否处于合理区间内，也即 【左子树max ，右子树min】之间。**
* **利用 Integer 是 object 的性质，用 null reference 代表开区间，避免 node 值为 Integer.MIN/MAX 的情况。**

```java
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    public boolean isValidBST(TreeNode root,Integer min, Integer max) {
        if(root == null) return true;

        if(min != null && root.val <= min) return false;
        if(max != null && root.val >= max) return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}
```

同样的，这题用 inorder traversal 也可以做，也不需要设全局变量。

```java
public boolean isValidBST(TreeNode root) {
   if (root == null) return true;
   Stack<TreeNode> stack = new Stack<>();
   TreeNode pre = null;
   while (root != null || !stack.isEmpty()) {
      while (root != null) {
         stack.push(root);
         root = root.left;
      }
      root = stack.pop();
      if(pre != null && root.val <= pre.val) return false;
      pre = root;
      root = root.right;
   }
   return true;
}
```

## [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)

这题考察的就是 BST 的性质: in order = sorted.

#### 另一种应对多次查询的好办法是 augmented binary tree; 第一次用 O(n) 的时间统计记录一下每个 node 左子树节点个数，后面的每次查询就可以 O(height) 的时间搜索了。

### Follow up:

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

维护一个大小为 k 的 max heap，一直有 insert 的时候好办；有 delete 而且删掉的 node 又在 heap 里就只好找一下 in order successor 了。

```java
PriorityQueue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());
```

```java
public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.pop();
            if(--k == 0) return node.val;
            cur = node.right;
        }

        return root.val;
    }
}
```

## [Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/)

简单写法是 naive 的 in order traversal. 只要是 binary tree 都可以用。

```java
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        boolean reachedP = false;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            if(reachedP) return node;
            if(node == p) reachedP = true;

            cur = node.right;
        }
        return null;
    }
}
```

* **不过这题还可以进一步利用 BST 的性质，不依赖 stack，只依靠值去模拟 inorder 的过程。**

```java
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode res = null;
    while(root!=null) {
        if(root.val > p.val) {
            res = root;
            root = root.left;
        }
        else root = root.right;
    }
    return res;
}
```

更像 in order 的写法是这样：

```java
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode rst = null;

        while(root != null){
            while(root != null && root.val > p.val){
                rst = root;
                root = root.left;
            }
            if(root != null) root = root.right;
        }

        return rst;
    }
}
```

## [Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)

利用 BST inorder = sorted 的性质，一道很有意思的递归题。

在 BST 里多用区间的思想思考问题。

```java
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private TreeNode helper(int[] nums, int start, int end){
        if(start > end) return null;
        if(start == end) return new TreeNode(nums[start]);

        int mid = start + (end - start) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, start, mid - 1);
        root.right = helper(nums, mid + 1, end);

        return root;
    }
}
```

## [Verify Preorder Sequence in Binary Search Tree](https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/)

* **只给定一个 preorder 顺序是无法生成唯一 binary tree 的，也可以生成多个 valid BST.**

所以这题的题意需要澄清下，正确意思是，给定一个 preorder sequence，只要这个 sequence 可以生成一个 valid BST，都返回 true.

这样我们的判断条件变成了这样，给定 array 如 5(123)(678)，第一个元素一定为 root，后面的比 root 小的连续序列为左子树，比 root 大的连续序列为右子树。

左右子树可以为空，但是不能违反 BST 子树性质。所以如果 > root 的连续数组后面又出现了 < root 的元素，一定是 false.

这题的写法上有点像 quicksort，要注意 index.

* **为了省心起见，这类 subarray 的 divide & conquer 最好把 length <= 2 的直接返回了，不然会多出许多 corner case 要考虑。**
* O(nlogn) time and O(1) space

```java
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        return helper(preorder, 0, preorder.length - 1);
    }

    private boolean helper(int[] preorder, int start, int end){
        if(end - start <= 1) return true;

        int breakPoint = start + 1;
        int root = preorder[start];

        // breakPoint should stop at index of first element > root
        // if no left subtree, breakPoint stops at start;
        for(int i = start + 1; i <= end; i++){
            if(preorder[i] < root) breakPoint ++;
            else break;
        }

        for(int i = breakPoint; i <= end; i++){
            if(preorder[i] < root) return false;
        }

        return helper(preorder, start + 1, breakPoint - 1) 
               && helper(preorder, breakPoint, end);
    }
}
```

## [Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)

* **Java 里一切都是 pass by value，当传入的是 object reference 的时候，实际传入的就是 object 的内存地址。**
* **因此，带泛型的各种数据结构，Stack, List 等，即使里面放的都是 TreeNode 并且进行了各种 add/remove/pop 操作，对这些 object 的修改也会反映到原来的 Tree 上。**

Hard 题，因为得 O(1) space. 这意味着做个 in order 存在 array 里面再扫的做法行不通，连 stack 也不能用了。。

先假设下我们有 inorder array，如何找那对 swapped pair ?

在中间 1234567 -> 1264537

在两端 1234567 -> 7234561

右端 1234567 -> 1237564

左端 1234567 -> 5234167

* **从左往右找递增序列里面第一个变小的，prev 为 swapped;**
* **从右往左找递减序列里面第一个变大的，prev 为 swapped.**
* **找错误元素可以简化成一次遍历，第一次找到违章元素，prev 是 swapped; 然后继续扫，第二次看到违章元素，cur 是 swapped.**

所以顺着这个思路的第一种暴力写法是建一个 arraylist 存 inorder traversal，然后扫两遍去找到底应该 swap 哪两个。然而 TLE 了，test case 故意坑人，教育我们不要一言不合就遍历。。。

```java
public class Solution {
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            list.add(node);
            cur = node.right;
        }

        if(list.size() == 2){
            swap(list.get(0), list.get(1));
            return;
        } 

        TreeNode p = null;
        TreeNode q = null;

        for(int i = 1; i < list.size(); i++){
            if(list.get(i).val < list.get(i - 1).val){
                p = list.get(i - 1);
                break;
            }
        }

        for(int i = list.size() - 2; i >= 0; i--){
            if(list.get(i + 1).val > list.get(i).val){
                q = list.get(i + 1);
                break;
            }
        }

        swap(p, q);

        return;
    }

    private void swap(TreeNode p, TreeNode q){
        if(p == null || q == null) return;
        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
}
```

于是改良版的写法是，先搞一个从左往右的 inorder，然后找第一个违章元素 on the fly.

然后做一个从右往左的 inorder，找第一个违章元素 on the fly.

这样不需要遍历整个 list，可以利用 early termination.

于是。。。卧槽，居然 AC 了？

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        TreeNode p = null;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            if(p == null){
                p = node;
            } else {
                if(node.val < p.val){
                    break;
                } else {
                    p = node;
                }
            }
            cur = node.right;
        }

        stack.clear();
        cur = root;
        TreeNode q = null;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.right;
            }
            TreeNode node = stack.pop();
            if(q == null){
                q = node;
            } else {
                if(node.val > q.val){
                    break;
                } else {
                    q = node;
                }
            }
            cur = node.left;
        }

        swap(p, q);

        return;
    }

    private void swap(TreeNode p, TreeNode q){
        if(p == null || q == null) return;
        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
}
```

### 遍历和迭代更简洁的写法在论坛[这个帖子](https://leetcode.com/discuss/68639/solutions-explanation-recursive-iterative-traversal-traversal)里写的非常好。

找错误元素可以简化成一次遍历，第一次找到违章元素，prev 是 swapped; 然后继续扫，第二次看到违章元素，cur 是 swapped.

### 递归版：

```java
public void recoverTree(TreeNode root) {
    //use inorder traversal to detect incorrect node

    inOrder(root);

    int temp = first.val;
    first.val = second.val;
    second.val = temp;
}

TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;

public void inOrder(TreeNode root){
    if(root == null) return;
    //search left tree
    inOrder(root.left);

    //in inorder traversal of BST, prev should always have smaller value than current value
    if(prev != null && prev.val >= root.val){
        //incorrect smaller node is always found as prev node
        if(first == null) first = prev;
      //incorrect larger node is always found as curr(root) node
        second = root;
    }

    //update prev node
    prev = root;

    //search right tree
    inOrder(root.right);
}
```

### 迭代版：

```java
public class Solution {
    public void recoverTree(TreeNode root) {

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        TreeNode prev = null;
        TreeNode p = null;
        TreeNode q = null;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();

            if(prev != null && node.val <= prev.val){
                if(p == null) p = prev;
                q = node;
            } 

            /* 上面这里如果写成这样，会在 [0,1] 的 case 上挂掉
               原因是只有两个 node 的情况下 q 还没来得及被赋值
               就结束了，于是 q == null 会导致无法 swap.
               拿掉那个 else 可以保证不管怎样 q 指向 cur node.
                if(p == null){
                    p = prev;
                } else {
                    q = node;
                }
            */
            prev = node;
            cur = node.right;
        }

        swap(p, q);
    }

    private void swap(TreeNode p, TreeNode q){
        if(p == null || q == null) return;
        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/531_tree-_bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.