# 669. Trim a Binary Search Tree

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:
1
/ \
0   2

L = 1
R = 2

Output:
1
\
2
``````

Example 2:

``````Input:
3
/ \
0   4
\
2
/
1

L = 1
R = 3

Output:
3
/
2
/
1
``````

``````class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (!root) return NULL;
if (root->val < L) return trimBST(root->right, L, R);
if (root->val > R) return trimBST(root->left, L, R);
root->left = trimBST(root->left, L, R);
root->right = trimBST(root->right, L, R);
return root;
}
};
``````

``````class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (!root) return NULL;
while (root->val < L || root->val > R) {
root = (root->val < L) ? root->right : root->left;
}
TreeNode *cur = root;
while (cur) {
while (cur->left && cur->left->val < L) {
cur->left = cur->left->right;
}
cur = cur->left;
}
cur = root;
while (cur) {
while (cur->right && cur->right->val > R) {
cur->right = cur->right->left;
}
cur = cur->right;
}
return root;
}
};
``````

https://discuss.leetcode.com/topic/102034/java-solution-6-liner

https://discuss.leetcode.com/topic/104140/java-solution-iteration-version

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation