【二叉树】修建二叉搜索树

解题思路：中序遍历递归解决

递归结束条件：传入结点为NULL

1.先检查root结点的值是否小于low，如果是，那么return trimBST(root->right)

2.再检查root是否大于high，如果是，那么return trimBST(root->left)

3.再将root->left设置为trimBST(root->left),root->right设置为trimBST(root->right),返回root

struct TreeNode* trimBST(struct TreeNode* root, int low, int high){
    if(!root)
        return NULL;
    
    if(root->val < low) {
        return trimBST(root->right, low, high);
    }
    else 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;
}

解题思路：迭代法解决

1.先将root转换到在low和high中间的结点

2.设置一个结点current。用这个结点遍历左子树和右子树：

a.如果左孩子存在时进行遍历。如果左孩子上的值小于low，将目前current的左孩子编程其左孩子的右孩子

b.对右孩子也是一样

3.返回root

struct TreeNode* trimBST(struct TreeNode* root, int low, int high){
    if(!root)
        return NULL;
    
    while(root && (root->val < low || root->val > high)) {
        if(root->val < low)
            root = root->right;
        else 
            root = root->left;
    }

    struct TreeNode* current = root;
    while(current) {
        while(current->left && current->left->val < low)
            current->left = current->left->right;
        current = current->left;
    }

    current = root;
    while(current) {
        while(current->right && current->right->val > high)
            current->right = current->right->left;
        current = current->right;
    }

    return root;
}