LeetCode 669. Trim a Binary Search Tree
撰写于 20180103 修改于 20180121 分类 LeetCode
Question:
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input:


Output:


Example 2:
Input:


Output:


Solution
The problem is pretty simple, follow the following steps and use recursion method
 If the val of current node is smaller than L, abandon the left subtree and trim its right subtree
 If the val of current node is greater than R, abandon the right subtree and trim its left subtree
 Else, recursively trim its left and right subtree and return the root
Code

