树与图中等2 种解法

#669修剪二叉搜索树

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

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

解题主线

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

解法 1：递归利用 BST 剪枝

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

时间复杂度

O(n) 最坏

空间复杂度

O(h)

669. 修剪二叉搜索树 · 递归利用 BST 剪枝

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) {
        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)

669. 修剪二叉搜索树 · 迭代修剪

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) {
        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