Remove every node whose value is outside the inclusive interval [low, high], and return the root of the remaining binary search tree. The root may change, and the result may be empty.
Preserve the relative structure of retained nodes: a retained descendant must remain a descendant of its retained ancestors. This determines one unique trimmed tree. Both boundary values are allowed to remain.
The input is a valid binary search tree with distinct values. Each node's left subtree contains smaller values, and its right subtree contains larger values. Examples use level-order arrays; null marks a missing child, and [] represents an empty result.
Example 1:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
low = 4
high = 13
Output: [8,6,10,4,7,null,13]Explanation: Remove 1 and 3 below the lower bound, connecting node 6 as the left child of 8. Remove 14 above the upper bound, connecting node 13 as the right child of 10. Values 4 and 13 remain because the bounds are inclusive.
Example 2:
Input: root = [5,2,8,1,3,7,9]
low = 6
high = 9
Output: [8,7,9]Explanation: The original root 5 and its whole left subtree are too small. Node 8 becomes the root, and its children 7 and 9 both remain.
Example 3:
Input: root = [4,2,6]
low = 7
high = 8
Output: []Explanation: Every node is smaller than 7. All nodes are removed, so the result is an empty tree.
Constraints:
- The input tree contains between 1 and 10000 nodes.
0 <= Node.val <= 10000- Node values are unique, and the input is a valid binary search tree.
0 <= low <= high <= 10000