# Java solution, recursion

• A typical recursion problem.

public class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null) return null;
return build(nums, 0, nums.length - 1);
}

private TreeNode build(int[] nums, int start, int end) {
if (start > end) return null;

int idxMax = start;
for (int i = start + 1; i <= end; i++) {
if (nums[i] > nums[idxMax]) {
idxMax = i;
}
}

TreeNode root = new TreeNode(nums[idxMax]);

root.left = build(nums, start, idxMax - 1);
root.right = build(nums, idxMax + 1, end);

return root;
}
}

• Sharing my solution, very similar idea, only differs slightly on base case handling. Also, the null input case is automatically handled.

public class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}

public TreeNode build(int[] nums, int lo, int hi) {
if (lo == hi)
return new TreeNode(nums[lo]);
int max = Integer.MIN_VALUE, maxIndex = lo;
for (int i = lo; i <= hi; i++) {
if (nums[i] > max) {
max = nums[i];
maxIndex = i;
}
}
TreeNode res = new TreeNode(max);
if (maxIndex - 1 >= lo)
res.left = build(nums, lo, maxIndex - 1);
if (maxIndex + 1 <= hi)
res.right = build(nums, maxIndex + 1, hi);
return res;
}
}

• This post is deleted!

• Same idea. Used copyOfRange to avoid helper function.

public class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length == 0) return null;
int idx = 0, iMax = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; i++){
if(nums[i] > iMax){
iMax = nums[i];
idx = i;
}
}
TreeNode root = new TreeNode(nums[idx]);
root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, idx));
root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, idx+1, nums.length));
return root;
}
}

• public class Solution {
private int getMax(int []arr,int l,int r){
int maxIndex = -1,max=Integer.MIN_VALUE;
for(int i=l;i<=r;i++){
if(max<arr[i]){
maxIndex=i;
max=arr[i];
}
}
return maxIndex;
}
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length==0)
return null;

TreeNode root= constructTree(nums,0,nums.length-1);
return root;
}
private TreeNode constructTree(int []nums,int l,int r){
if(l>r)
return null;
int maxIdx = getMax(nums,l,r);
TreeNode treeNode = new TreeNode(nums[maxIdx]);
treeNode.left= constructTree(nums,l,maxIdx-1);
treeNode.right = constructTree(nums,maxIdx+1,r);

return treeNode;
}

}

• @shawngao is the worst case run time of this n^2 because when the input is 6,5,4,3,2,1 we travel the array for every every node entirely to check for the max element! ??

• idxMax can be written into indexMax.
Just a suggestion. You only type two more letters but much better for reading and understanding, especially in companies

• @sushant_gupta Yes, the worst case run time is O(n^2).

• @BHC Ha, thanks for your suggestion.

• does it help if we use TreeMap<Integer,List<Integer>>, where value will be the list of index and the key will be array value?

• In average, is the time complexity O(NlogN)? If the tree is balanced? Or in worst case O(N*N) If the tree has N levels?

• Is this solution acceptable in an interview? I fear that the interviewer would want a faster solution than O(n^2)

public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree(nums, 0, nums.length - 1);
}

private TreeNode constructMaximumBinaryTree(int[] nums, int s, int e) {
if(s > e) return null;
int max = getMax(nums, s, e);
TreeNode root = new TreeNode(nums[max]);
root.left = constructMaximumBinaryTree(nums, s, max-1);
root.right = constructMaximumBinaryTree(nums, max+1, e);
return root;
}

private int getMax(int[] nums, int s, int e){
int max = e;
for(int i=s;i<e;i++){
if(nums[i] > nums[max]) max = i;
}
return max;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.