Java simple recursive solution with explanation


  • 0

    Search for the maximum element's index within a lower and an upper bound. Construct a node with the max element,
    set the left and right subtrees of this node as the result of calling construct with lower and upper bounds upto and from
    the max element's index.

    public class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            return construct(nums, 0, nums.length - 1);    
        }
        
        private TreeNode construct(int[] nums, int lo, int hi) {
            if(hi < lo) {
                return null;
            }
            
            int maxIndex = findMaxIndex(nums, lo, hi);
            
            TreeNode node = new TreeNode(nums[maxIndex]);
            node.left = construct(nums, lo, maxIndex - 1);
            node.right = construct(nums, maxIndex + 1, hi);
            
            return node;
        }
        
        private int findMaxIndex(int[] nums, int lo, int hi) {
            int max = nums[lo], maxIndex = lo;
            for(int i = lo + 1; i <= hi; i++) {
               if(nums[i] > max) {
                   max = nums[i];
                   maxIndex = i;
               }
            }
            
            return maxIndex;
        }
    }
    

Log in to reply
 

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