669. Prune binary search tree ●●

669. Prune the binary search tree ●●

Give you the root node of the binary search tree root , At the same time, the minimum boundary is given low And the maximum boundary high. By pruning the binary search tree , Make the values of all nodes in [low, high] in . Pruning trees Should not be Change the relative structure of the elements retained in the tree ( namely , If not removed , The original relationship between father and son should be preserved ). Can prove that , There is The only answer .

Input ：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output ：[3,2,null,1]

For binary search trees ,
If root->val < low, Then the pruned binary tree must appear on the right of the root node ;
If root->val > high, Then the pruned binary tree must appear on the left of the root node .

recursive

Time complexity ：O(N), among N Are all the nodes of a given tree . We can visit each node at most once .
Spatial complexity ：O(N), Even if we don't explicitly use any additional memory , In the worst case , The stack of our recursive calls may be as large as the number of nodes .

• Traverse from top to bottom , After pruning a node , You need to judge this node again （ Return to the pruned subtree ）;

class Solution {
    
public:
    TreeNode* pre = nullptr;
    TreeNode* trimBST(TreeNode* root, int low, int high) {
    
        if(root == nullptr) return nullptr;
        if(root->val < low){
    
            return trimBST(root->right, low, high);	//  Return to the pruned right subtree 
        }else if(root->val > high){
    
            return trimBST(root->left, low, high);	//  Return to the pruned left subtree 
        }
        root->left = trimBST(root->left, low, high);	//  Prune the left subtree 
        root->right = trimBST(root->right, low, high);	//  Prune right subtree 
        return root;
    }
};

• From the bottom up , Pruning the subtree does not affect the structure of the nodes above , At the same time, you can traverse the whole tree without re judging a node .

class Solution {
    
public:
    TreeNode* pre = nullptr;
    TreeNode* trimBST(TreeNode* root, int low, int high) {
    
        if(root == nullptr) return nullptr;
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        if(root->val < low){
    		
            // root->left = nullptr; //  Delete left subtree 
            return root->right;		//  And replace the node with a right subtree 
        }else if(root->val > high){
    
            // root->right = nullptr; //  Delete the right subtree 
            return root->left;		//  And replace the node with the left subtree 
        }
        return root;
    }
};

iteration

Due to the orderliness of the search tree , Therefore, there is no need to use the stack to simulate the recursive process , The process is ：

1. First put the root node root Move to the range , Determine the new root node ;
2. Handle unqualified nodes in the left subtree of the current root node ;
3. Handle unqualified nodes in the right subtree of the current root node .

class Solution {
    
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
    
        if(root == nullptr) return nullptr;
        //  Determine the root node in the interval 
        while(root != nullptr){
             
            if(root->val < low){
    
                root = root->right;
            }else if(root->val > high){
    
                root = root->left;
            }else{
    
                break;
            }
        }
        //  here root Already in [low, high]  Within the scope of , Handle left child element less than low The situation of 
        TreeNode* curr = root;
        while(curr != nullptr){
    
        	// 【 Notice that this is while loop , Until we find the qualified  > low  Replace the left child node of 】
            while(curr->left != nullptr && curr->left->val < low){
    		
                curr->left = curr->left->right;
            }
            curr = curr->left;
        }
        //  here root Already in [low, high]  Within the scope of , Deal with the right child high The situation of 
        curr = root;
        while(curr != nullptr){
    
        	// 【 Notice that this is while loop 】
            while(curr->right != nullptr && curr->right->val > high){
    	
                curr->right = curr->right->left; 
            }
            curr = curr->right;
        }

        return root;
    }
};