BST

inorder 是BST的核心

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

Closest Binary Search Tree Value

根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。 所以我们根据这个递归，返回子树中最近的节点，和根节点中更近的那个就行了。保证target的值是在根节点和某个子树的值中间就可以找到最近的了。

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

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

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

    // inorder traverse all node
    // maintain a closest variable 
    // update it with the traverse
    public double find(TreeNode root, double target, Integer closest) {
        if(root == null) return -1;
        if(closest == null) closest = root.val;

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

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

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

        return closest;

    }

    // more concise solution
    public int closestValue(TreeNode root, double target) {
        TreeNode child = root.val > target ? root.left : root.right;

        if(child == null) return root.val;
        // post-order
        int closest = closestValue(child, target);

        return Math.abs(root.val - target) > Math.abs(closest - target) ? closest : root.val;
    }

}

Validate Binary Search Tree

在 BST 中定义 “区间”，即对于一个正在考虑的 root，检查值是否处于合理区间内，也即 【左子树max ，右子树min】之间。

利用 Integer 是 object 的性质，用 null reference 代表开区间，避免 node 值为 Integer.MIN/MAX 的情况。

public class Solution {
    // 这个做法有一个case 过不去，就是当root.val 是 max value 或者 min value.
    // 改进的写法就是用null来代表开区间
    public boolean isValidBST(TreeNode root) {
        return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

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

        if(root.val <= min || root.val >= max) return false;

        // 尾递归写法
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

    // version 2
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

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

        // 不能有重复的值
        if(min != null && root.val <= min || max != null && root.val >= max) return false;

        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}

Kth Smallest Element in a BST

BST的inorder是有序的

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

        // error-prone: || 
        while(!stack.isEmpty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            k--;
            if(k == 0) {
                return node.val;
            }

            cur = node.right;
        }
        return root.val;
    }
}

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?

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

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

Inorder Successor in BST

常规用stack的写法

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        boolean reachP = false;

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

            cur = node.right;
        }       
        // if the node don't have successor
        return null;
    }
}

我们可以是用bst的特点，inorder的successor 也就是比p节点的值要大的节点，因此当我们要go left的时候，我们就要记录当前节点，这个节点就有可能是successor。

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

Predecessor or Successor node of BST

Input: root node, key output: predecessor node, successor node

本质上是找最后一个记录的拐点。 predecessor 是记录右拐 successor 是记录左拐。

1. If root is NULL then return
2. if key is found then a. If its left subtree is not null

    Then predecessor will be the right most child of left subtree or left child itself.
   

   b. If its right subtree is not null

    The successor will be the left most child 
    of right subtree or right child itself.
   

   return
3. If key is smaller then root node

    set the successor as root
    search recursively into left subtree
   

   else

    set the predecessor as root
    search recursively into right subtree
   

public TreeNode inOrderPredecessorRec(TreeNode root, TreeNode p) {
    if (root == null) {
        return null;
    }
    // inorder traverse
    // 在root上直接判断
    if (root.val >= p.val) {
        return inOrderPredecessorRec(root.left,p);
    } else {
        TreeNode right = inOrderPredecessorRec(root.right,p);
        return (right != null) ? right : root;
    }

}


public TreeNode inOrderSuccessorRec(TreeNode root, TreeNode p) {
    if (root == null) {
        return null;
    }

    if (root.val <= p.val) {
        return inOrderSuccessorRec(root.right,p);
    } else {
        TreeNode left = inOrderSuccessorRec(root.left,p);
        return (left != null) ? left : root;
    }
}

迭代解法

Inorder Successor

BST 里面，任意位置，任意楼层，都可以通过 value 的比较确定相对位置，这是 BST 一个最好用的性质。

因此在 BST 里面，确定起来就很简单了，从 root 往下走，每次往左拐的时候，存一下，记录着最近一个看到的比 p.val 大的 node 就行了。

public TreeNode inOrderSuccessor(TreeNode root, TreeNode p) {
    TreeNode result = null;

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