Recursive Solution, Beats 95.6% of Submissions


  • 0
    S

    The way i approached this was to keep track of the current boundaries of where i am in the array. So at the beginning my left boundary is 0 and my right boundary is the end of the array. I start by looking for the maximum value to be my current node and its index. This index will partition the input array into two parts. The left part is where my current node's left child will be and the right part is where the right child will be. So I do recursive callsto my function once for the left partition where my left boundary will be the same but my right boundary will the maximum index -1. And another recursive call for the right partition where the left boundary is the maximum index+1 and the right boundary is the current right boundary. It all bottoms out when the left boundary surpasses the right boundary.

    public class Solution {
        public TreeNode helper(int [] nums, int left, int right) {
            if(left > right)
                return null;
            int max = Integer.MIN_VALUE;
            int index = -1;
            for(int i=left; i<=right; i++) {
                if(nums[i]>max) {
                    max = nums[i];
                    index = i;
                }
            }
            TreeNode node= new TreeNode(max);
            node.left = helper(nums, left, index-1);
            node.right = helper(nums, index+1, right);
            return node;
        } 
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            return helper(nums, 0, nums.length-1);
        }
    }
    

Log in to reply
 

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