What is the main challenge in trimming a binary search tree?

The main challenge is efficiently trimming the tree while maintaining its binary search tree properties, ensuring the structure remains valid after removal of out-of-range nodes.

How do I handle nodes that lie outside the given range?

You discard nodes outside the range by adjusting the tree structure, either removing left or right children based on whether the node is too small or too large.

What traversal technique should I use to trim a binary search tree?

A Depth-First Search (DFS) traversal is ideal for this problem, as it allows you to process each node recursively and adjust the tree accordingly.

How do I optimize my solution for large trees?

To optimize the solution for large trees, focus on efficient traversal and ensure that unnecessary operations are minimized. Also, consider iterative approaches to avoid deep recursion.

Can the root of the tree change after trimming?

Yes, the root of the tree may change after trimming if the original root node falls outside the specified range.

#669

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high 。通过修剪二叉搜索树，使得所有节点的值在 [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⁴

lightbulb

解题思路

方法一：递归

判断 root.val 与 low 和 high 的大小关系：

若 root.val 大于 high，说明当前 root 节点与其右子树所有节点的值均大于 high，那么递归修剪 root.left 即可；
若 root.val 小于 low，说明当前 root 节点与其左子树所有节点的值均小于 low，那么递归修剪 root.right 即可；
若 root.val 在 [low, high] 之间，说明当前 root 应该保留，递归修剪 root.left, root.right，并且返回 root。

递归的终止条件是 root 节点为空。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉搜索树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBST(
        self, root: Optional[TreeNode], low: int, high: int
    ) -> Optional[TreeNode]:
        def dfs(root):
            if root is None:
                return root
            if root.val > high:
                return dfs(root.left)
            if root.val < low:
                return dfs(root.right)
            root.left = dfs(root.left)
            root.right = dfs(root.right)
            return root

        return dfs(root)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluates understanding of tree traversal techniques like DFS.
question_mark
Tests ability to modify the tree while maintaining binary search tree properties.
question_mark
Assesses problem-solving skills in handling edge cases and large input sizes.

warning

常见陷阱

外企场景

error
Misunderstanding the impact of trimming on tree structure, leading to incorrect child node connections.
error
Incorrectly handling edge cases, such as an empty tree or a tree where all nodes fall outside the range.
error
Not maintaining the binary search tree property after trimming the tree.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Trimming with different range boundaries, such as low = 0 and high = 10, testing the ability to handle various boundary values.
arrow_right_alt
Trimming a more complex tree with a larger number of nodes, increasing the challenge in tree traversal and modification.
arrow_right_alt
Handling trees where all nodes are within the specified range, ensuring no unnecessary trimming occurs.

help

常见问题

外企场景

继续练习

#653 两数之和 IV - 输入二叉搜索树 #783 二叉搜索树节点最小距离 #538 把二叉搜索树转换为累加树