二叉搜索树系列

1. 判断是否为二叉搜索树

public boolean isBinaryTree(TreeNode root, TreeNode min, TreeNode max) {
    if(root == null)
        return true;
    if(min != null && root.val <= min.val) return false;
    if(max != null && root.val >= max.val) return false;
    return isBinaryTree(root.left, min, root) 
        && isBinaryTree(root.right, root, max);
}

class Solution {
    long min = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null)
            return true;
        if(isValidBST(root.left) && root.val > min) {
            min = root.val;
            return isValidBST(root.right);
        }
        else
            return false;
    }
}

2. 判断一个树是否存在

boolean isInBST(TreeNode root, int target) {
    if(root == null)
        return false;
    if(root.val == target)
        return true;
    if(target < root.val)
        return isInBST(root.left, target);
    if(target > root.val)
        return isInBST(root.right, target);
}

3. 插入节点

1. root为空，返回一个值为val的新节点
2. root不为空：
   1. val < root.val：插入到左子树
   2. val > root.val：插入到右子树

TreeNode insert(TreeNode root, int val) {
    if(root == null)
        return new TreeNode(val);
    if(val < root.val)
        root.left = insert(root.left, val);
    if(val > root.val)
        root.right = insert(root.right, val);
    return root;
}

4. 删除元素

1. 当找到节点时：
   1. 如果左右子树都为null，返回null
   2. 如果一个子树为空，返回不为空的子树
   3. 如果子树都不为空，找到右子树中的最小值，作为根节点的值，然后删除该节点
2. val小于当前节点值：遍历左子树
3. val大于当前节点值：遍历右子树

TreeNode delete(TreeNode root, int val) {
    if(root == null)
        return null;
    if(root.val == val) {
        if(root.left == null)
            return right;
      	if(root.right == null)
            return left;
        root.val = getMin(root.right).val;
        root.right = delete(root.right, root.val);
    }
    else if(val < root.val)
        root.left = delete(root.left, val);
    else if(val > root.val)
        root.right = delete(root.right, val);
}

TreeNode getMin(TreeNode root) {
    // BST 最左边的就是最小的
    while(root.left != null)
        root = root.left;
    return root;
}