654. Maximum binary tree
Give a non repeating integer array nums. The maximum binary tree can be constructed recursively from nums with the following algorithm:
Create a root node with the maximum value in nums.
Recursively construct the left subtree on the subarray prefix to the left of the maximum.
Recursively construct the right subtree on the subarray suffix to the right of the maximum.
Returns the largest binary tree constructed by nums.
Example 1:
Input: num = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: recursive calls are as follows:
- The maximum value in [3,2,1,6,0,5] is 6, the left part is [3,2,1], and the right part is [0,5].
- The maximum value in [3,2,1] is 3, the left part is [], and the right part is [2,1].
- Empty array, no child nodes.
- The maximum value in [2,1] is 2, the left part is [] and the right part is [1].
- Empty array, no child nodes.
- There is only one element, so the child node is a node with a value of 1.
- The maximum value in [0,5] is 5, the left part is [0], and the right part is [].
- There is only one element, so the child node is a node with a value of 0.
- No sub nodes, no sub arrays.
- The maximum value in [3,2,1] is 3, the left part is [], and the right part is [2,1].
Example 2:
Input: num = [3,2,1]
Output: [3,null,2,null,1]
reflection
In fact, this itself is a recursion, and the topic is also described more clearly
First, write a function getmaxindex (int [] num, int left, int right) to get the index of the maximum value of the num function in the left to right range.
Initialization before recursion:
Get the index of the maximum value of the num function and build the root node
Initialize the intervals rootleft0, rootleft1, rootright0 and rootright1 of the left and right subtrees of root in the array and initialize them to - 1. Its - 1 indicates that there is no left and right subtree in the root node
Next, determine whether there are left and right subtrees
-If the root node is equal to 0, there is no left subtree in the root node
-If the root node is equal to num Length-1, there is no right subtree in the root node
If there are left and right subtrees, assign values to them
Recursive constructtotree (root, num, rootleft0, rootleft1, rootright0, rootright1)
First, you don't need to return a value because root is a reference variable.
Its parameters need the range of nodes, arrays and left and right subtrees of its nodes.
Recursive end condition, which does not have left and right subtrees, i.e. rootleft0 = = - 1 & & rootright0 = = - 1
Initialize left=null, right=null
If the root node has a left subtree
- Gets the index of the maximum value of the left subtree leftMaxindex Value construction to point to root.left
- Next, we think leftMaxindex The value pointed to is the root node of the left subtree leftTreeRoot
- We need to judge the root node leftTreeRoot Whether there are left and right subtrees
- There are left and right subtrees
- Recursion
- There are only right subtrees
- Recursion
- Only left subtree exists
- Recursion
be careful:There are no left and right subtrees, so there is no need to operate
If the root node has a right subtree
- It is similar to the above and will not be repeated
public static TreeNode constructMaximumBinaryTree(int[] nums) {
int maxIndex = getMaxIndex(nums,0,nums.length-1);
TreeNode root = new TreeNode(nums[maxIndex]);
int rootleft0 = -1;
int rootleft1 = -1;
int rootright0 = -1;
int rootright1 = -1;
if(maxIndex>0){
rootleft0 = 0;
rootleft1 = maxIndex-1;
}
if(maxIndex<nums.length-1){
rootright0 = maxIndex+1;
rootright1 = nums.length-1;
}
constructToTree(root,nums,rootleft0,rootleft1,rootright0,rootright1);
return root;
}
private static void constructToTree(TreeNode root, int[] nums, int rootleft0, int rootleft1, int rootright0, int rootright1) {
if(rootleft0==-1&&rootright0==-1) return;
TreeNode left = null;
TreeNode right = null;
// Left subtree exists
if(rootleft0!=-1){
int leftMaxIndex = getMaxIndex(nums, rootleft0, rootleft1);
left = new TreeNode(nums[leftMaxIndex]);
root.left = left;
int hasleft = 1;
int hasright = 1;
if(leftMaxIndex ==rootleft0) hasleft=0;
if(leftMaxIndex ==rootleft1) hasright =0;
// The maximum value of the left subtree as the root node has left and right subtrees
if(hasleft==1&&hasright==1){
constructToTree(root.left,nums,rootleft0,leftMaxIndex-1,leftMaxIndex+1,rootleft1);
}
// The maximum value of the left subtree as the root node has only the left subtree
if(hasleft==1&&hasright==0){
constructToTree(root.left,nums,rootleft0,leftMaxIndex-1,-1,-1);
}
// Only right subtree
if(hasleft==0&&hasright==1) {
constructToTree(root.left,nums,-1,-1,leftMaxIndex+1,rootleft1);
}
//There is neither left subtree nor right subtree, and no operation is required
}
if(rootright0!=-1){
int rightMaxIndex = getMaxIndex(nums, rootright0, rootright1);
right = new TreeNode(nums[rightMaxIndex]);
root.right = right;
int hasleft = 1;
int hasright = 1;
if(rightMaxIndex ==rootright0) hasleft=0;
if(rightMaxIndex ==rootright1) hasright =0;
// There are left and right subtrees
if(hasleft==1&&hasright==1){
constructToTree(root.right,nums,rootright0,rightMaxIndex-1,rightMaxIndex+1,rootright1);
}
// Only left subtree
if(hasleft==1&&hasright==0){
constructToTree(root.right,nums,rootright0,rightMaxIndex-1,-1,-1);
}
// Only right subtree
if(hasleft==0&&hasright==1) {
constructToTree(root.right,nums,-1,-1,rightMaxIndex+1,rootright1);
}
//There is neither left subtree nor right subtree, and no operation is required
}
}
public static int getMaxIndex(int[] nums,int left,int right){
int max = nums[left];
int index = left;
for (int i = left; i<=right;i++){
if(nums[i]>max) {
max = nums[i];
index = i;
}
}
return index;
}