Java solution, recursion


  • 6

    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;
        }
    }
    

  • 0

    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;
        }
    }
    

  • 0
    This post is deleted!

  • 0
    S

    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;
        }
    }
    

  • 0
    P

    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;
    }
    

    }


  • 0
    S

    @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! ??


  • 0

    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


  • 0

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


  • 0

    @BHC Ha, thanks for your suggestion.


  • 0
    S

    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?


Log in to reply
 

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