LeetCode 669. 修剪二叉搜索树

约 4 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
深度优先搜索 树 二叉树 二叉搜索树

题目描述

✅ 669. 修剪二叉搜索树

image-20260928224502140

image-20260928224502143

题意分析

删除二叉搜索树中值不在闭区间 [low, high] 内的节点，同时保留剩余节点原来的祖先后代关系和左右方向。被删除的节点可以由其合法后代接替位置，所以原根也可能变化，必须返回修剪后的新根。

解法：递归裁剪

核心思路

[!blue]

定义 trimBST(root, low, high) 返回当前子树修剪完成后的根。这样无论当前节点保留还是删除，父层都只需要把对应孩子指针接到返回值上。

若 root.val < low，左子树的所有值比当前值还小，当前节点和整棵左子树都必须删除；合法节点只可能出现在右子树中，因此直接返回右子树递归修剪后的根。若 root.val > high，当前节点和整棵右子树都过大，同理返回左子树的修剪结果。

若当前值位于区间内，就保留当前节点，分别修剪左右子树，并把返回的新根接回 root.left、root.right。不能只调用递归而忽略返回值，因为孩子自身可能被删除，需要由更深的节点接替。

空树直接返回空。由这个边界逐层向上，每个返回结果都只含合法节点；接回来的左右子树仍来自原来的对应分支，所以不会打乱 BST 的大小关系，也不会交换保留节点的祖先关系。整个过程只重接必要的边，不需要重建或旋转树。

解题步骤

  1. 当前节点为空时，返回空。
  2. 当前值小于 low，返回 trimBST(root.right, low, high)。
  3. 当前值大于 high，返回 trimBST(root.left, low, high)。
  4. 当前值合法，分别修剪左右子树并保存返回的根节点，然后返回当前节点。

等于 low 或 high 都应保留；如果整棵树没有合法值，递归最终会沿候选方向走到空节点并返回空。

代码实现

// 若节点值大于 high，则整棵右子树都被裁掉，返回裁剪后的左子树。
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;
    }
}

// 若节点值大于 high，则整棵右子树都被裁掉，返回裁剪后的左子树。
func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }

    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
}

复杂度分析

  • 时间复杂度：$O(n)$ 上界，其中 $n$ 是原树节点数。每个访问到的节点只处理一次，被判定全部越界的子树无需继续访问。
  • 空间复杂度：$O(h)$，递归栈深度不超过原树高度 $h$；树退化成链时最坏为 $O(n)$。

关键点总结

[!green]

  • 递归返回的是修剪后的新根，既能表示保留当前节点，也能表示由后代接替或整棵为空。
  • BST 的全局大小关系使整侧剪枝成立，而不是只判断当前节点是否合法。
  • 合法节点保留，左右孩子只接回原分支的修剪结果，原有相对结构得以维持。

易错点总结

[!yellow]

  • 当前节点越界就直接返回空，会连带丢掉另一侧仍可能合法的后代。
  • 递归调用后不接收返回根，父节点还会保留指向被删节点的旧连接。
  • 使用 <= low 或 >= high 剪枝，会错误删除合法的边界值。
  • 不能只原地修改后仍固定返回原根，因为根本身也可能需要删除。

相似题目

题目 难度 关联与区别
450. 删除二叉搜索树中的节点 中等 同样删除BST节点，本题按值域批量裁剪，可直接舍弃完全位于范围外的一侧子树。
98. 验证二叉搜索树 中等 BST的全局大小约束让剪枝合法，不能把范围判定仅视为普通树的局部节点删除。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/52815758
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！