树与图中等2 种解法

#669修剪二叉搜索树

删除值不在闭区间 [low, high] 内的节点，并保持原节点相对结构。

#二叉搜索树#递归#迭代

原题

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

树中节点数在范围 [1, 10⁴] 内
0 <= Node.val <= 10⁴
树中每个节点的值都是唯一的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 10⁴

查看原题

解题主线

根值小于 low 时整棵左子树都应丢弃，大于 high 时整棵右子树都应丢弃。

解法 1：递归利用 BST 剪枝

越界时直接返回可能含有效值的一侧；区间内则递归修剪两侧。

时间复杂度： O(n) 最坏
空间复杂度： O(h)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        // 利用 BST 有序性：根过小时整棵左子树都可丢弃，过大时反之。
        // 保留下来的节点只需重接可能仍含合法值的一侧，原相对结构不变。
        if (root == null) return null;
        if (root.val < low) return trimBST(root.right, low, high);
        if (root.val > high) return trimBST(root.left, low, high);
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

解法 2：迭代修剪

先沿正确方向找到区间内的新根，再分别重接左侧过小链和右侧过大链。

时间复杂度： O(h)；每次只沿 BST 边界链移动
空间复杂度： O(1)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        // 利用 BST 有序性：根过小时整棵左子树都可丢弃，过大时反之。
        // 保留下来的节点只需重接可能仍含合法值的一侧，原相对结构不变。
        while (root != null && (root.val < low || root.val > high)) {
            root = root.val < low ? root.right : root.left;
        }
        if (root == null) return null;

        TreeNode current = root;
        while (current != null) {
            while (current.left != null && current.left.val < low) {
                current.left = current.left.right;
            }
            current = current.left;
        }

        current = root;
        while (current != null) {
            while (current.right != null && current.right.val > high) {
                current.right = current.right.left;
            }
            current = current.right;
        }
        return root;
    }
}

边界与易错点

原迭代代码寻找有效根的方向写反：过小应向右，过大应向左。
找到有效根后，左链只处理过小节点，右链只处理过大节点。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q669_trimBST.java