Leetcode 669 pruning binary search tree -- recursive method and iterative method

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/trim-a-binary-search-tree

---

The question ：

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 .

So the result should return the new root node of the pruned binary search tree . Be careful , The root node may change according to the given boundary .

Example 1：

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

Example 2：

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

Tips ：
The number of nodes in the tree is in the range [1, 10⁴] Inside
0 <= Node.val <= 10⁴
The value of each node in the tree is only Of
Topic data input is an effective binary search tree
0 <= low <= high <= 10⁴

---

Reference article

Ideas ：

Let's start with the recursive method ：

Recursive method , You need to determine the parameters of the recursive method first 、 Return value . In fact, this problem involves the reconstruction of binary tree , So with the help of recursive method, return the form of node , It simplifies the code .

• When the current node traversed is less than the minimum value , Then the nodes in its left subtree are also less than the lowest value , We traverse directly to its right subtree .
• Empathy , When the current node traversed is greater than the maximum value , Then the nodes in its right subtree are also greater than the lowest value , We traverse directly to its left subtree .
• If the value of the current node is in the range , Then this node is reserved , Let's traverse its left and right subtrees to see if there is anything to refactor , Finally, return the current node to

Recursive method Java Code ：

class Solution {
    
    public TreeNode trimBST(TreeNode root, int low, int high) {
    
        if (root == null) return null;
        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;
    }
}

The following is the idea of iterative method ：

First, we will root Adjust to nodes in the range , Then we'll talk about root Cut the nodes that are not in the range in the left and right subtrees of .

So how to cut ？

If it is traversing to the current node , Judge whether the current node is within the range , If it's not in range , Then discard the current node , In this way , You need to record the parent node of the current node （ In other topics, you may also need to record whether the current node is the left node or the right node of the parent node ）, This will be more troublesome .

Then let's just Judge whether the child node of the current node needs to be cut , If the child node of the current node is not in the range , We directly use the son node of the son node to replace the son node of the current node （ I didn't expect it to be a little windy ）. Do this , It is much more convenient in cutting operation ！

Iterative method Java Code ：

class Solution {
    
    public TreeNode trimBST(TreeNode root, int low, int high) {
    
        // First adjust root To the extent 
        while (root != null && (root.val < low || root.val > high)) {
    
            if (root.val < low) root = root.right;
            else root = root.left;
        }
        TreeNode cur = root;
        // cut off root Nodes not in the range in the left subtree 
        while (cur != null) {
    
            while (cur.left != null && cur.left.val < low) cur.left = cur.left.right;
            cur = cur.left;
        }
        cur = root;
        // cut off root Nodes not in the range in the right subtree 
        while (cur != null) {
    
            while (cur.right != null && cur.right.val > high) cur.right = cur.right.left;
            cur = cur.right;
        }
        return root;
    }
}