###### tags: `Leetcode` `medium` `tree` `python` `c++`

# 669. Trim a Binary Search Tree

## [題目連結:] https://leetcode.com/problems/trim-a-binary-search-tree/description/

## 題目:
Given the ```root``` of a binary search tree and the lowest and highest boundaries as ```low``` and ```high```, trim the tree so that all its elements lies in ```[low, high]```. Trimming the tree should **not** change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a **unique answer**.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.


## 解題想法:
* 此題為修剪BST，給出邊界範圍low,high，所有不在此範圍的node需移除
* 因為BST性質: 左.val<root.val<右.val
* 遞迴求解:
* 若當前root.val<low:
* 表示root.left皆更小於low，皆不符合
* return 遞迴(root.right,low,high)
* 若當前root.val>high:
* 表示root.right皆大於high,皆不符合
* return 遞迴(root.left, low, high)
* 正常遞迴:
* root.left=遞迴(root.left, low, high)
* root.right=遞迴(root.right, low, high)
* return root

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def trimBST(self, root, low, high):
        """
        :type root: TreeNode
        :type low: int
        :type high: int
        :rtype: TreeNode
        """
        if not root:
            return 
        if root.val<low: #若root太小 自己與左子全捨棄
            return self.trimBST(root.right,low,high)
        elif root.val>high: #若root太大 自己與右子全捨棄
            return self.trimBST(root.left,low,high)
        else: #root在安全範圍 遞規檢查左右子
            root.left=self.trimBST(root.left,low,high)
            root.right=self.trimBST(root.right,low,high)
            return root

root=TreeNode(3)
root.insertLeft(0)
root.insertRight(4)
root.left.insertRight(2)
root.left.right.insertLeft(1)
root.printTree()

result=Solution()
low=1
high=3
ans=result.trimBST(root,low,high)
ans.printTree()

## C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
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;
    }
};