Recursive construction of maximum binary tree

654. The largest binary tree

Medium difficulty

Given an array of non repeating integers nums . The largest binary tree You can use the following algorithm from nums Build... Recursively :

1. Create a root node , Its value is nums Maximum of .
2. Recursively at maximum On the left Of Subarray prefix Build the left subtree .
3. Recursively at maximum On the right Of Subarray suffix Build the right subtree .

return nums Built The largest binary tree .

Ideas

This problem can be solved by recursion , Similar to the solution of fast platoon

We find the maximum in the current range , Then recurse its left and right ranges constantly , Repeatedly find the maximum value of the current range and recurse , Until the length of the interval is 0

package cn.edu.xjtu.carlWay.tree.maximumBinaryTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 654.  The largest binary tree  *  Given an array of non repeating integers  nums .  The largest binary tree   You can use the following algorithm from  nums  Build... Recursively : * <p> *  Create a root node , Its value is  nums  Maximum of . *  Recursively at maximum   On the left   Of   Subarray prefix   Build the left subtree . *  Recursively at maximum   On the right   Of   Subarray suffix   Build the right subtree . *  return  nums  Built   The largest binary tree  . * <p> * https://leetcode-cn.com/problems/maximum-binary-tree/ */
public class Solution {
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    
        return helpConstruct(nums, 0, nums.length);
    }

    private TreeNode helpConstruct(int[] nums, int left, int right) {
    
        //  No element in interval 
        if (left == right) {
    
            return null;
        }
        //  There is one element left in the interval 
        if (right - left == 1) {
    
            return new TreeNode(nums[left]);
        }
        int maxIdx = findMaxIdx(nums, left, right);//  Find the maximum value of the current interval 
        TreeNode root = new TreeNode(nums[maxIdx]);

        root.left = helpConstruct(nums, left, maxIdx);//  Recursive processing 
        root.right = helpConstruct(nums, maxIdx + 1, right);//  Recursive processing 
        return root;
    }

    /** *  Find the maximum value of the current interval  * * @param nums * @param left * @param right * @return */
    private int findMaxIdx(int[] nums, int left, int right) {
    
        int max = nums[left];
        int maxIdx = left;
        for (int i = left; i < right; i++) {
    
            if (nums[i] > max) {
    
                max = nums[i];
                maxIdx = i;
            }
        }
        return maxIdx;
    }
}