BST

• 递归时，要考虑状态可能的不连续性。

• 取左右子树的 min/max 之后加上当前节点是最常见的递归结构，保证了 path 自顶向下的连续。

• BST 做 in order traversal 得到的结果是 sorted.

• BST 中 root 的左子树所有点小于 root; 右子树所有点大于 root.

• 一个正确的 BST 中每一个点都有其合理的取值闭区间，为【左子树 max , 右子树 min】，最左右两端的点为一端开放区间。

• 维护大小为 k 的 MaxHeap:

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

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

Closest Binary Search Tree Value

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

• 所以一要存好 prev;

• 二要两边都探，不能沿着一边硬走。

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;
    }
}

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

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

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

• 多研究下 subtree 的结构和性质，目前对这个理解还不够。

• 递归时，要考虑状态可能的不连续性，这题和 Binary Tree Maximum Path Sum 很像。

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

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 的情况。

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 也可以做，也不需要设全局变量。

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

这题考察的就是 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 了。

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

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

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

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 的过程。

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 的写法是这样：

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

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

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

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

• 只给定一个 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

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

• 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 故意坑人，教育我们不要一言不合就遍历。。。

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 了？

/**
 * 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;
    }
}

遍历和迭代更简洁的写法在论坛这个帖子里写的非常好。

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

递归版：

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);
}

迭代版：

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;
    }
}