跳到主要内容

二叉搜索树

二叉搜索树 (BST) 的核心性质是：左子树 < 根 < 右子树。这意味着对 BST 进行中序遍历会得到一个递增序列。

530. 二叉搜索树的最小绝对差 (Minimum Absolute Difference in BST)​

题目描述​

给你一个二叉搜索树的根节点 root ，返回 树中任意两个不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

解题思路​

中序遍历 + 前驱节点比较。

  1. 维护全局变量 pre 记录上一个遍历到的节点值。
  2. 递归中序遍历。
  3. 计算 root.val - pre 并更新全局最小值。

Java 代码实现​

class Solution {
    int min = Integer.MAX_VALUE;
    Integer pre = null;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;
    }
    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if (pre != null) min = Math.min(min, root.val - pre);
        pre = root.val;
        dfs(root.right);
    }
}

230. 二叉搜索树中第 K 小的元素 (Kth Smallest Element in a BST)​

题目描述​

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

解题思路​

中序遍历计数。

  1. 递增遍历 BST。
  2. 定义计数器 count。当 count == k 时，当前节点值即为所求。

Java 代码实现​

class Solution {
    int res, k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if (--k == 0) { res = root.val; return; }
        dfs(root.right);
    }
}

98. 验证二叉搜索树 (Validate Binary Search Tree)​

题目描述​

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

解题思路​

中序遍历严格递增。

  1. BST 的中序遍历序列必须是严格单调递增。
  2. 维护 long pre (考虑到边界使用 Long.MIN_VALUE) 记录前一个值。
  3. 如果 root.val <= pre 返回 false。

Java 代码实现​

class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (root.val <= pre) return false;
        pre = root.val;
        return isValidBST(root.right);
    }
}

(注：也可以通过递归传递 (min, max) 范围进行判定)。