問題（Easy）：
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:
大意：
給出一個二叉查找樹和最小、最大邊界L和R，修剪樹使其所有元素都在[L, R]（R >= L）中。你可能需要改變樹的根節(jié)點，所以結(jié)果應(yīng)該返回裁剪后的樹的新跟節(jié)點。
例1：
輸入：
輸出：
例2：
輸入：
輸出：
思路：
題目的意思就是讓樹只保留L到R范圍內(nèi)的數(shù)字，但是還是要保證樹是個二叉查找樹，雖然題目說了可能要改變根節(jié)點，但實際上只有根節(jié)點不在范圍內(nèi)的時候才需要更改。
思路就是遞歸遍歷樹的每個節(jié)點，將其看做根節(jié)點，判斷是否為空、是否在范圍內(nèi)。如果不在，則要根據(jù)大小取左子節(jié)點或者右子節(jié)點作為新的根節(jié)點；如果在，則繼續(xù)判斷左右子節(jié)點。就直接用遞歸來做。
要注意每次遞歸都會在一開始就判斷根節(jié)點是否為空，所以不用在遞歸前又去判斷子節(jié)點是否為空，實測這將節(jié)省大量時間
代碼：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (root == NULL) return NULL;
TreeNode *res = root;
if (root->val > R)
res = trimBST(root->left, L, R);
else if (root->val < L)
res = trimBST(root->right, L, R);
else {
res->left = trimBST(res->left, L, R);
res->right = trimBST(res->right, L, R);
}
return res;
}
};
他山之石：
除了用遞歸，也可以用循環(huán)來做，就循環(huán)判斷左右子樹，看大小是否在范圍內(nèi)，在則繼續(xù)往下，否則將其左/右子節(jié)點作為當(dāng)前循環(huán)的節(jié)點。
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
// find the proper root
while(root->val<L || root->val>R)
{
if(root->val<L) { root = root->right; }
else { root = root->left; }
}
// temporary pointer for left and right subtree
TreeNode *Ltemp = root;
TreeNode *Rtemp = root;
// remove the elements larger than L
while(Ltemp->left)
{
if( (Ltemp->left->val)<L ) { Ltemp->left = Ltemp->left->right; }
else { Ltemp = Ltemp->left; }
}
// remove the elements larger than R
while(Rtemp->right)
{
if( (Rtemp->right->val)>R) { Rtemp->right = Rtemp->right->left; }
else { Rtemp = Rtemp->right; }
}
return root;
}
};
合集：https://github.com/Cloudox/LeetCode-Record
