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``。 自建示例 -------- 原根仍然保留: .. code-block:: text 输入:root = [3,1,4,null,2],low = 2,high = 4 输出:[3,2,4] 解释:值 1 超出区间被删除,它的合法右孩子 2 接回原来的祖先关系中;3 和 4 保留。 所有节点都超出区间: .. code-block:: text 输入:root = [1,0,2],low = 3,high = 4 输出:null 解释:树中没有节点值落在 [3,4] 内,因此修剪结果为空树。