Java solution, recursion


  • 14

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


  • 1

    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?


  • 1
    M

    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?


Log in to reply
 

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