654. Maximum Binary Tree

654. Maximum Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return getMaximumNodeHelper(nums,0,nums.length - 1, new TreeNode(0));
    }

    public static TreeNode getMaximumNodeHelper(int[] nums, int start, int end, TreeNode n){
        if(start == end && start  end) return null;

        int maxValue = Integer.MIN_VALUE;
        int maxIndex = 0;

        for (int i = start; i  maxValue){
                maxValue = nums[i];
                maxIndex = i;
            }
        }
         n.val = maxValue;
        ///
        int maxValueRight = Integer.MIN_VALUE;
        int maxIndexRight = maxIndex+1;
        for (int i = maxIndex+1; i  maxValueRight){
                maxValueRight = nums[i];
                maxIndexRight = i;
            }
        }
        n.right = getMaximumNodeHelper(nums,maxIndex+1,end,new TreeNode(maxValueRight));
        ////
        int maxValueLeft = Integer.MIN_VALUE;
        int maxIndexLeft = maxIndex+1;
        for (int i = start; i  maxValueLeft){
                maxValueLeft = nums[i];
                maxIndexLeft = i;
            }
        }
        n.left =  getMaximumNodeHelper(nums,start,maxIndex-1,new TreeNode(maxValueLeft));

        return n;
    }
}

Alternative better Solution

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s