0669. Trim a Binary Search Tree¶
题目信息¶
- 题号:
0669
- 难度:
Medium
- 主题:
二叉搜索树、闭区间、删除节点、相对结构保留
- 原题:
- 重点:
只保留值位于 [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] 内,因此修剪结果为空树。