修剪二叉搜索树

记住「太小丢自己+左子树、换右边;太大丢自己+右子树、换左边;在范围内才递归剪左右」,下面逐帧套它。

修剪二叉搜索树：先看这棵 BST:根 50,左边 30(挂着 20、40)、右边 70(挂着 60、80)。要保留的区间是 [35, 65],我们从根开始递归修剪。

修剪二叉搜索树：先找感觉:BST 里任何节点,它的左子树整棵都比它小、右子树整棵都比它大。所以一个节点一旦越界,它越界那一侧的整棵子树必然也越界,可以整段丢——这正是本题能一遍 O(n) 裁完的根。

修剪二叉搜索树：从根 50 开始。50 落在 [35, 65] 里,是要保留的节点。

修剪二叉搜索树：50 保留(标绿)。接下来按规则,要分别去修剪它的左子树和右子树。

修剪二叉搜索树：先修剪左子树,来到 30。先和下界 35 比一比。

修剪二叉搜索树：30 < 35,比下界还小,30 这个节点越界,必须丢掉。

修剪二叉搜索树：更关键的是:BST 里 30 的整个左子树(这里是 20)都比 30 还小,自然也都 < 35。所以 30 连同它的左边 20 整段都丢掉,只可能在它的右子树里还有合格的节点。

修剪二叉搜索树：于是把 50 的左孩子改接到 30 的右子树 40 上,30 和 20 已不在树里。现在继续修剪新接上来的 40。

修剪二叉搜索树：40 落在 [35, 65] 里,保留。

修剪二叉搜索树：40 保留(标绿)。它没有左右孩子,继续递归下去都是空,左子树这一支就修剪完了。

修剪二叉搜索树：左子树这一支全部处理完,50 的左边现在挂的就是 40。接下来回到 50,去修剪它的右子树。

修剪二叉搜索树：左边修好,回到 50 修剪右子树,来到 70。和上界 65 比一比。

修剪二叉搜索树：70 > 65,比上界还大,70 越界,要丢掉。

修剪二叉搜索树：同样地,BST 里 70 的整个右子树(这里是 80)都比 70 还大、也都 > 65,所以 70 连同右边 80 整段丢掉,只可能在它的左子树里还有合格节点。

修剪二叉搜索树：所以只保留 70 的左子树 60 这一支,把它接到 50 的右边顶替 70 的位置。70 和 80 即将从树上离开。

修剪二叉搜索树：把 50 的右孩子改接到 70 的左子树 60 上,70 和 80 已不在树里。继续修剪 60。

修剪二叉搜索树：60 落在 [35, 65] 里,保留。

修剪二叉搜索树：60 保留(标绿)。它也是叶子,右子树这一支修剪完成。

修剪二叉搜索树：整棵树修剪完成:只剩 50、40、60 三个节点,而且它们原来的相对位置(40 在左、60 在右)保持不变。

修剪二叉搜索树：验证一下:修剪后中序遍历是 40、50、60,严格升序、仍是合法 BST,且每个值都落在 [35, 65] 里,符合要求。

修剪二叉搜索树：回头看:每到一个节点,值太小就连同左子树一起丢、换上修剪后的右子树;值太大就连同右子树一起丢、换上左子树;在范围内才保留并递归修剪左右。BST 的有序性让我们能「整段剪」,一遍递归 O(n) 就裁好了。

边界:空树返回空;全在界内原样返回;全越界裁成空树。

两个追问:比 lc450 删点简单(整段裁);可改迭代做到 O(1) 空间。