669. Pruning a Binary Search Tree

Give you the root node root of the binary search tree, and give the minimum boundary low and the maximum boundary high. By pruning the binary search tree, the values ​​of all nodes are in [low, high]. Pruning the tree should not change the relative structure of the elements that remain in the tree (i.e., the original parent-child relationship should be preserved if not removed). It can be shown that there is a unique answer.

So the result should return the new root node of the pruned binary search tree. Note that the root node may change according to the given bounds.

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]

hint:

• The number of nodes in the tree is in the range [1, 104]
• 0 <= Node.val <= 104
• The value of each node in the tree is unique
• The title data guarantees that the input is a valid binary search tree
• 0 <= low <= high <= 104

exist 235. Nearest Common Ancestor of a Binary Search Tree, 701. Insertion Operations in a Binary Search Tree, 450. Deleting a Node in a Binary Search Tree It has been implemented to delete nodes in the binary search tree, and pruning the binary search tree can be regarded as deleting all nodes outside the interval. This can also use the nature of searching binary trees. For example, if a node is cut because the value is less than the interval value, and all the node values ​​​​of the left subtree of this node must be smaller than this node, they can all be deleted. Then let the parent of this node The node is directly connected to the right subtree of this node, which obviously can greatly reduce the operation. In the same way, similar operations can be performed when a node larger than the interval value is cut off.

Another difference from the delete node operation is that to delete a node, you only need to find the node to be deleted, delete it and perform some operations, even without traversing the entire binary search tree. And pruning needs to delete all unqualified nodes. The above pruning operation can greatly reduce the deletion operation, but there may still be unqualified nodes in the connected subtree, so continue to traverse down.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {   // If the value of the node is less than low, return the result after pruning its right subtree
            return trimBST(root.right, low, high);
        } else if (root.val > high) {   // If the value of the node is greater than high, return the result after pruning its left subtree
            return trimBST(root.left, low, high);
        } else {    // root is in the range of [low,high]
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
            return root;
        }
    }
}

 

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums whose elements have been sorted in ascending order, please convert it into a height-balanced binary search tree.

 

A height-balanced binary tree is a binary tree that satisfies "the absolute value of the height difference between the left and right subtrees of each node does not exceed 1".

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] will also be considered the correct answer:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height balanced binary search trees.

hint:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums in strictly increasing order

If there is no requirement for high balance, it will be simple. Now that there is a requirement, the key is to find the intermediate node. To be highly balanced, each recursion must find the number in the middle of the interval. The left side of this number is the value of the left subtree, and the right side is the value of the right subtree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }
    private TreeNode traversal(int[] nums, int left, int right) {
        if (left > right)   return null;
        int mid = (left + right) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root;
    }
}

There is another problem that needs to be paid attention to when cutting an array, that is, whether the range of the new array to be cut is left-closed and right-closed or left-closed and right-opened? Depending on the selection, the steps are also subtly different. For this question, it is recommended to use left-closed-right-closed. When left=right, the intermediate node root=left=right is a leaf node and can be returned directly.

538. Convert Binary Search Tree to Accumulating Tree

Given the root node of the binary search tree, the tree has different node values, please convert it into a cumulative tree (Greater Sum Tree), so that the new value of each node node is equal to or greater than or equal to node in the original tree. The sum of the values ​​of val .

As a reminder, a binary search tree satisfies the following constraints:

• A node's left subtree contains only nodes whose keys are less than the node's key.
• A node's right subtree contains only nodes whose keys are greater than the node's key.
• The left and right subtrees must also be binary search trees.

Note: This question and 1038: Leek  same

Example 1:

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

Example 3:

Input: root = [1,0,2]
Output: [3,3,2]

Example 4:

Input: root = [3,2,4,1]
Output: [7,9,4,10]

hint:

• The number of nodes in the tree is between 0 and 104.
• Each node has a value between -104 and 104.
• All values ​​in the tree are distinct from each other.
• The given tree is a binary search tree.

We generally use in-order traversal for binary search trees, but for this question to find an accumulative tree, we finally use the reverse order traversal of in-order traversal, that is, right-middle-left to traverse the binary tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        traversal(root);
        return root;
    }

    // Traverse in the order of right, middle and left, and accumulate
    public void traversal(TreeNode root) {
        if (root == null)   return;
        traversal(root.right);
        sum += root.val;
        root.val = sum;
        traversal(root.left);
    }
}

An idea similar to double pointers is used here, but the results of accumulation and sums are directly used instead of pointer traversal.