0669. Trim a Binary Search Tree

题目信息

题号:

0669

难度:

Medium

主题:

二叉搜索树、闭区间、删除节点、相对结构保留

原题:

LeetCode 0669

重点:

只保留值位于 [low,high] 的节点、结果仍需是 BST、保留节点之间原有祖先后代关系、根节点可能改变或变为空

题目重述

给定二叉搜索树根节点 root 和整数 low、high,删除所有节点值不在闭区间 [low, high] 内的节点,返回修剪后树的根节点。

修剪结果必须保留原树中所有合法节点,并保持它们原有的相对结构;不能重新排列节点来构造另一棵 BST。原树节点值互不相同,节点数位于 [1, 10^4],节点值以及 low、high 位于 [0, 10^4],且 low <= high。

自建示例

原根仍然保留:

输入:root = [3,1,4,null,2],low = 2,high = 4
输出:[3,2,4]
解释:值 1 超出区间被删除,它的合法右孩子 2 接回原来的祖先关系中;3 和 4 保留。

所有节点都超出区间:

输入:root = [1,0,2],low = 3,high = 4
输出:null
解释:树中没有节点值落在 [3,4] 内,因此修剪结果为空树。