###### tags: `LeetCode` `Tree` `Recursion` `Medium`
# LeetCode #669 [Trim a Binary Search Tree](https://leetcode.com/problems/trim-a-binary-search-tree/)
### (Medium)(第一次沒做出來)

給你二元搜索樹的根節點 root ，同時給定最小邊界low 和最大邊界 high。通過修剪二元搜索樹，使得所有節點的值在[low, high]中。修剪樹不應該改變保留在樹中的元素的相對結構（即，如果沒有被移除，原有的父代子代關係都應當保留）。可以證明，存在唯一的答案。

所以結果應當返回修剪好的二元搜索樹的新的根節點。注意，根節點可能會根據給定的邊界發生改變。

---
判斷條件:
* 若root不存在, 回傳空指標
* 若root的值小於low, 則回傳trimBST(root->right, low, high)
*(因為是二元搜尋樹, 若root小於low, 則整個左子樹都會小於low, 從右子樹開始處理)*
* 若root的值大於high, 則回傳trimBST(root->left, low, high)
*(理由同上, 這次從左子樹開始處理)*
* 若皆不符合以上判斷條件, 代表root在範圍內, 接下來處理左右子節點並回傳root。
---

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root)return nullptr;
        if(root->val<low)return trimBST(root->right, low, high);
        if(root->val>high)return trimBST(root->left, low, high);
        root->left=trimBST(root->left, low, high);
        root->right=trimBST(root->right, low, high);
        return root;
    }
};