Menu Sidebar
Menu

Tree

Trim a Binary Search Tree

给一个BST, 然后给一个L和R两个整数, 给BST剪枝(trim), 问剪枝后的树. 这个题很有意思, 首先要理解剪枝这个操作, 仅仅是针对当前node的. 而对于node的子树,需要重新判断, 那么这个题就是一个子问题划分的题, 我们要通过递归不断把问题分解. 通过观察example, 我们可以看出, node.val如果大于R, 那么node的右边的子树都大于R, 那么都应该剪掉, 所以返回node的左边, 并且继续子问题探索. 同理对node.val小于R的情况. 如果node.val在L和R之间, 那么我们只需要继续分开讨论左边和右边子问题即可.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

April 2024
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
2930