定义

一棵二叉搜索树具有以下特征

节点的左子树只包含小于当前节点的数
节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

例题

98. 验证二叉搜索树

验证一棵二叉树，需要判断当前节点是否在某个合理的范围区间（down、upper）。

class Solution {
  public boolean isValidBST(TreeNode root) {
      if (root == null) return true;
      return validBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
  }
  private boolean validBST(TreeNode root, long down, long upper) {
      if (root == null) return true;
      int val = root.val;
      if (val >= upper || val <= down) return false;
      return validBST(root.left, down, val) && validBST(root.right, val, upper);
  }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode prev = null;
        TreeNode p = root;
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.addLast(p);
                p = p.left;
            }

            TreeNode node = stack.pollLast();
            if (prev != null && prev.val >= node.val)  {return false;}
            p = node.right;
            prev = node;
        }

        return true;
    }
}

530. 二叉搜索树的最小绝对差

递归思路

使用一个指针记录前面的节点，利用中序遍历和 BST 特性，让当前值和 prev 指针相比较，得到最小值。

class Solution {
    private int res = Integer.MAX_VALUE;
    private TreeNode prev;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        inorder(root);
        return res;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null) res = Math.min(res, Math.abs(root.val - prev.val));
        prev = root;
        inorder(root.right);
    }
}

501. 二叉搜索树中的众数

class Solution {
    private List<Integer> res = new ArrayList<>();
    TreeNode prev = null;
    int curCount = 0;
    int maxCount = 0;

    public int[] findMode(TreeNode root) {
        if (root == null) return new int[0];

        inorder(root);

        int[] array = new int[res.size()];
        int j = 0;
        for (Integer ele : res) {
            array[j++] = ele;
        }
        return array;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);

        if (prev == null) {
            curCount++;
        } else if (prev.val == root.val) {
            curCount++;
        } else {
            curCount = 1;
        }
        if (maxCount == curCount) {
            res.add(root.val);
        } else if (curCount > maxCount){
            res.clear();
            res.add(root.val);
            maxCount = curCount;
        }
        prev = root;

        inorder(root.right);
    }
}

class Solution {

    public int[] findMode(TreeNode root) {
        if (root == null) return new int[0];
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode prev = null;
        TreeNode p = root;
        int maxCount = 0;
        int curCount = 0;

        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.addLast(p);
                p = p.left;
            }

            TreeNode node = stack.pollLast();
            if (prev == null) {
                curCount = 1;
            } else if (prev.val == node.val) {
                curCount++;
            } else {
                curCount = 1;
            }

            if (maxCount == curCount) {
                res.add(node.val);
            } else if (curCount > maxCount){
                res.clear();
                maxCount = curCount;
                res.add(node.val);
            }

            p = node.right;

            prev = node;
        }

        int[] array = new int[res.size()];
        int i = 0;
        for (Integer n : res) {
            array[i++] = n;
        }
        return array;
    }
}

235. 二叉搜索树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;
        int rootVal = root.val;
        // 左边
        if (p.val < rootVal && q.val < rootVal) {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if (left != null) return left;
        } 

        // 右边
        if (p.val > rootVal && q.val > rootVal) {
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (right != null) return right;
        }

        // 如果分叉了，那么就只能返回根节点了
        return root;
    }
}

701. 二叉搜索树中的插入操作

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

450. 删除二叉搜索树中的节点

BST 树删除操作比较麻烦，需要对不同节点排布情况做不同处理：

没有左、右子节点，置空。
只有一个非空子节点。那么让这个孩子替换自己的位置。
存在两个子节点，这是最麻烦的情况。为了保证不破坏 BST 的性质，需要找到左子树中最大的那个节点，或者右子树中最小的那个节点来替换自己的位置。

BST删除操作1.jpg

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            // 相等，root节点需要被删除
            // #1 找到右子树的最左节点
            if (root.left == null || root.right == null) 
                return root.left == null ? root.right : root.left; 
            TreeNode minLeft = findMin(root.right);
            root.val = minLeft.val;
            root.right = deleteNode(root.right, minLeft.val);
        }

        return root;
    }

    private TreeNode findMin(TreeNode node) {
        if (node == null) return null;
        TreeNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
}

某些代码的删除操作会增加树的高度。

669. 修剪二叉搜索树

合理利用 BST 树的有序性。

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return root;
        if (root.val > high) return trimBST(root.left, low, high);
        if (root.val < low) return trimBST(root.right, low, high);
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

108. 将有序数组转换为二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        if (nums.length == 1) return new TreeNode(nums[0]);
        return buildT(nums, 0, nums.length);
    }

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

        // 这么分割数组是会存在问题的
        int mid = start + ((end - start) / 2);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildT(nums, start, mid);
        root.right = buildT(nums, mid + 1, end);

        return root;
    }
}