108. Convert Sorted Array to Binary Search Tree
Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced
binary search tree.
Example 1:
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
Example 2:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0){
return null;
}
if(nums.length == 1){
return new TreeNode(nums[0]);
}
int size = nums.length;
int mid = nums.length>>1;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid+1, size));
return root;
}
we only need to consider dividing the original array into two nearly the same size sub-arrays. Then link the part to the middle element and do it iteratively.
538. Convert BST to Greater Tree
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [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]
Constraints:
The number of nodes in the tree is in the range [0, 104].
-104 <= Node.val <= 104
All the values in the tree are unique.
root is guaranteed to be a valid binary search tree.
Original Page
Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
According to the description the new node value will be added to the sum of the value that is larger than itself and this is a BST. Thus, it implies that we can process the logic from the rightest node (has biggest value) -> then middle -> then left.
A reverse version of an in-order transverse (right -> middle -> left)
public TreeNode convertBST(TreeNode root) {
if(root == null){
return root;
}
greaterWork(root, 0);
return root;
}
public int greaterWork(TreeNode cur, int cumulate){
if(cur.left == null && cur.right == null){
cur.val += cumulate;
cumulate = cur.val;
return cur.val;
}
if(cur.right!=null){
cumulate = greaterWork(cur.right, cumulate);
}
cur.val += cumulate;
cumulate = cur.val;
if(cur.left != null){
cumulate = greaterWork(cur.left, cumulate);
}
return cumulate;
}
Method 2 we can refine this code by editing end logic use node == null instead of node == leaf node;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return root;
}
greaterWork(root, 0);
return root;
}
public int greaterWork(TreeNode cur, int cumulate){
if(cur == null){
return cumulate;
}
cumulate = greaterWork(cur.right, cumulate);
cur.val += cumulate;
cumulate = cur.val;
cumulate = greaterWork(cur.left, cumulate);
return cumulate;
}
}
Method 3 we can use the method that build a global variable instead of a parameter of the new method
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return root;
}
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);
return root;
}
669. Trim a Binary Search Tree
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.
Return the root of the trimmed binary search tree. Note that the root may change depending on 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]
Constraints:
The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 10^4
The value of each node in the tree is unique.
root is guaranteed to be a valid binary search tree.
0 <= low <= high <= 10^4
Wrong Code here
Debuging
class Solution {
/**
find low
find high
1. partent link
2. child link
a. low left child parent drop
b, low right child parent fill in
a. high left child fill in
b. high right child drop
*/
// TreeNode cur;
TreeNode parent;
TreeNode preParent;
boolean isLeft;
public TreeNode trimBST(TreeNode root, int low, int high) {
TreeNode cur = root;
parent = root;
findTarget(cur, low);
System.out.println(parent.val);
System.out.println(cur.val);
if(cur.val == root.val){
root.left = null;
}
if(cur!=null){
System.out.println("not null");
if(cur.right == null){
if(isLeft){
preParent.left = null;
} else{
preParent.right = null;
}
} else{
System.out.println("low right not null");
if(isLeft){
preParent.left = cur.right;
}else{
preParent.right = cur.right;
}
}
}
cur = root;
parent = root;
findTarget(cur, high);
System.out.println(parent.val);
System.out.println(cur.val);
if(cur == root){
cur.right = null;
}
if(cur!=null){
if(cur.left == null){
if(isLeft){
parent.left = null;
} else{
parent.right = null;
}
} else{
if(isLeft){
parent.left = cur.left;
}else{
parent.right = cur.left;
}
}
}
return root;
}
public TreeNode findTarget(TreeNode cur, int target){
if(cur == null){
return null;
}
TreeNode result = findTarget(cur.left, target);
if(result !=null){
return result;
}
if(cur.val == target){
return cur;
}
preParent = parent;
parent = cur;
return findTarget(cur.right, target);
}