Leetcode brush questions: binary tree 18 (largest binary tree)

654. The largest binary tree

Force button topic address

Given an array of integers without repeating elements . A maximum binary tree constructed from this array is defined as follows ：

• The root of a binary tree is the largest element in the array .
• The left subtree is the largest binary tree constructed from the left part of the maximum value in the array .
• Right subtree is the largest binary tree constructed by the right part of the maximum value in the array .

Build the largest binary tree from a given array , And output the root node of the tree .

Example ：

Tips ：

The size of the given array is [1, 1000] Between .

Traverse , Find the maximum value and its position . The array is divided into left and right subtree arrays . Create nodes and add left and right subtrees . The recursive termination condition is that the left and right arrays are empty , That is, the leaf node .

package com.programmercarl.tree;

/** * @ClassName ConstructMaximumBinaryTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 15:45 * @Version 1.0 * 654.  The largest binary tree  * https://leetcode.cn/problems/maximum-binary-tree/ **/
public class ConstructMaximumBinaryTree {
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    
        if (nums.length == 0) {
    
            return null;
        }
        int max = -1;
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
    
            if (nums[i] > max) {
    
                max = nums[i];
                maxIndex = i;
            }
        }
        // Find the current maximum 
        TreeNode root = new TreeNode(nums[maxIndex]);
        // 6 - 3 = 3
        int[] leftNums = new int[maxIndex];
        // 6 - 3 - 1 = 2
        int[] rightNums = new int[nums.length - maxIndex - 1];
        for (int i = 0; i < nums.length; i++) {
    
            if (i < maxIndex) {
    
                leftNums[i] = nums[i];
            } else if (i > maxIndex) {
    
                rightNums[i - maxIndex - 1] = nums[i];
            }
        }
// System.out.println(leftNums);
// System.out.println(rightNums);
        root.left = constructMaximumBinaryTree(leftNums);
        root.right = constructMaximumBinaryTree(rightNums);
        return root;
    }

    public static void main(String[] args) {
    
        new ConstructMaximumBinaryTree().constructMaximumBinaryTree(new int[]{
    3,2,1,6,0,5});
    }
}