This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

1. The subject

Given an integer array nums with no repeating elements. A maximum binary tree built directly recursively from this array is defined as follows:

The root of a binary tree is the largest element in the array NUMs. The left subtree is the largest binary tree constructed recursively from the left part of the maximum value in the array. The right subtree is the largest binary tree constructed recursively from the part to the right of the maximum value in the array. Returns the largest binary tree built with the given array NUMs.

Example 1:

Output: input: nums =,2,1,6,0,5 [3] [6,3,5, null, 2, 0, null, null, 1] : recursive calls as shown below: The maximum value in - [3,2,1,6,0,5] is 6, the left part is [3,2,1], and the right part is [0,5]. The maximum value in - [3,2,1] is 3, the left part is [], and the right part is [2,1]. - An empty array with no child nodes. - the maximum value in [2,1] is 2, the left part is [], and the right part is [1]. - An empty array with no child nodes. - There is only one element, so a child node is a node with a value of 1. The maximum value in - [0,5] is 5, the left part is [0], and the right part is []. - There is only one element, so a child node is a node with a value of 0. - An empty array with no child nodes.Copy the code

Example 2:

Input: nums = [3,2,1] Output: [3, NULL,2,null,1]Copy the code

2.

For the binary tree problem, all the root node has to do is figure out how to construct itself.

We must go through the array to find the maximum maxVal, make the root node root, and then recursively call the left and right arrays of maxVal as the left and right subtrees of root.

For each root node, you just need to find the maximum value in the current NUMS and the corresponding index, and then recursively call the left and right arrays to construct the left and right subtrees

See the code for details:

class Solution {    // Classical recursion
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length-1);
    }
​
    /* Construct nums[lo..hi] into a tree and return the root node */
    public TreeNode build(int[] nums, int begin, int end){
        if(begin > end){
            return null;
        }
        // Find the maximum value of the array and its corresponding index
        int maxValue = Integer.MIN_VALUE;
        int index = -1;
        for(int i = begin; i <= end; i++){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                index = i;
            }
        }
        TreeNode maxNode = new TreeNode(maxValue);
        // Recursive calls construct left and right subtrees
        maxNode.left = build(nums, begin, index-1);
        maxNode.right = build(nums, index+1, end);
        returnmaxNode; }}Copy the code

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast