669. Trim a Binary Search Tree
问题
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
DFS搜索,每次递归带上搜索的范围值。
如果当前节点小于搜索范围,递归当前节点的右子节点。
反之递归当前节点的左子节点。
如果当前节点在搜索范围中,则其左子节点等于递归后的左子节点,右子节点等于递归后的右子节点。
然后返回当前节点。
1 | /** |
669. Trim a Binary Search Tree
https://xuanhe95.github.io/2022/04/16/669-Trim-a-Binary-Search-Tree/