669. Pruning of binary search trees
Given the root node of a binary search tree, and given the minimum boundary low and the maximum boundary high, prune the binary search tree so that all nodes have values in [low, high]. Pruning the tree should not change the relative structure of the elements that remain in the tree (i.e., if they are not removed, the original parent-child relationships should be preserved). 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 depending on the given boundaries.
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]
Tip:
The number of nodes in the tree is in the range [1, 104] Inside.
0 <= <= 104
The value of each node in the tree is unique.
The topic data guarantees that the input is a valid binary search tree
0 <= low <= high <= 104
correct solution (a math. equation)
- Determination of termination conditions
The pruning operation is not performed on the termination condition, so it's just a matter of returning to an empty node when it encounters one. - Determining the logic of single-level recursion
If the element of root (the current node) is less than the value of low, then the right subtree should be recursed and the eligible head node of the right subtree should be returned.
If the elements of root (the current node) are greater than HIGH, then the left subtree should be recursed and the eligible head node of the left subtree should be returned.
The next step is to assign the result of the next layer after processing the left subtree to root->left, and the result after processing the right subtree to root->right. - Finally, the root node is returned
Upcode (●'◡'●)
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr ) return nullptr;
if (root->val < low) {
TreeNode* right = trimBST(root->right, low, high); // Finding Conforming Intervals[low, high]nodes
return right;
}
if (root->val > high) {
TreeNode* left = trimBST(root->left, low, high); // Finding Conforming Intervals[low, high]nodes
return left;
}
root->left = trimBST(root->left, low, high); // root->leftAccess to eligible left children
root->right = trimBST(root->right, low, high); // root->rightAccess to eligible right children
return root;
}
};
Streamlining:
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) 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;
}
};
108. Converting an ordered array to a binary search tree
You are given an array of integers, nums, whose elements are sorted in ascending order.
Balanced binary search trees.
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 as the correct answer:
Example 2:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both highly balanced binary search trees.
Tip:
1 <= <= 104
-104 <= nums[i] <= 104
nums in strictly ascending order
correct solution (a math. equation)
It is actually natural for arrays to construct binary trees that form balanced trees;
Because everyone defaults to taking values from the middle of the array as node elements, they are generally not randomized.
So trying to form unbalanced binary trees is asking for trouble.
The essence is to find the split point, which is used as the current node, and then recursively left and right intervals.
The split point is the node in the middle position of the array.
So for the question comes, if the array length is even and there are two middle nodes, which one to take?
Taking either one is fine, except that it constitutes a different balanced binary search tree.
- Determining the return value of a recursive function and its arguments
Deleting binary tree nodes and adding binary tree nodes is done with the return value of the recursive function, which is more convenient.
Then the question is to construct a binary tree, still using the return value of the recursive function to construct the left and right children of the center node.
Looking at the parameters again, the first thing you pass is the array, then the left subscript left and the right subscript right
Try not to redefine the left and right interval arrays when constructing a binary tree, but instead use subscripts to manipulate the original array. - Determining recursive termination conditions
The interval defined here is left-closed-right-closed, so when the interval left > right is empty node. - Determining the logic of single-level recursion
First take the position of the middle element of the array, it's not hard to write int mid = (left + right) / 2;
One problem with this is that the values are out of bounds, for example, left and right are both max int's, so this would be out of bounds.
So it can be written like this: int mid = left + ((right - left) / 2);
With the middle position taken, start constructing the node with the element at the middle position, code: TreeNode* root = new TreeNode(nums[mid]);.
The interval is then divided, with root's left child catching the constructed nodes of the next left interval, and the right child catching the constructed nodes of the next right interval.
Finally return to root
Upcode (●'◡'●)
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, () - 1);
return root;
}
};