Binary tree - 654. Maximum binary tree

1 Title Description

Given an array of non repeating integers nums. The maximum binary tree can be obtained from nums Build... Recursively :
1. Create a root node , Its value is nums Maximum of .
2. Recursively construct the left subtree on the prefix of the subarray to the left of the maximum .3. Recursively construct the right subtree on the subarray suffix to the right of the maximum . return num5 Maximum binary tree constructed .

2 Title Example

Input ：nums = [3,2,1,6,0,5]
Output ：[6,3,5,null,2,0,null,null,1]
explain ： The recursive call looks like this ：

• [3,2,1,6,0,5] The maximum value in is 6 , The left part is [3,2,1] , The right part is [0,5] .
  • [3,2,1] The maximum value in is 3 , The left part is [] , The right part is [2,1] .
    • An empty array , No child nodes .
    • [2,1] The maximum value in is 2 , The left part is [] , The right part is [1] .
      • An empty array , No child nodes .
      • There's only one element , So the child node is a value of 1 The node of .
  • [0,5] The maximum value in is 5 , The left part is [0] , The right part is [] .
    • There's only one element , So the child node is a value of 0 The node of .
    • An empty array , No child nodes .

Topic example source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/maximum-binary-tree

3 Topic tips

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums All integers in Different from each other

4 Ideas

Method 1 : recursive
This method is very simple . Create method construct(nums,1,r), Used to find in the array nums In the from l To , Indexes ( It doesn't include , A place ) The root node of the largest binary tree in .
The algorithm steps are as follows :

1. First call construct(nums,0, n), among n It's an array nums
   The length of .
2. In index range (l : r―1) Index to find the maximum value in , take nums[max_ department ] As root node .
3. call construct(nums,1,max_i) Create the left child of the root node . Perform this operation recursively , Create the entire left subtree of the root node .
4. Allied , call construct(nums,max_i + 1,r) Create the right subtree of the root node .
5. Method construct(nums,0, n) Returns the root node of the largest binary tree .

Complexity analysis
. Time complexity :o(n²). Method construct— Called together n Time . Every time you recursively find the root node , You need to traverse all elements in the current index range to find the maximum value . In general , The complexity of each traversal is O(log n), The total complexity is o(n logn). At worst , Array Tums Orderly , The total complexity is O(n²).
. Spatial complexity :O(n). Recursive call depth is n. On average , The length is n The recursive call depth of the array is O(log n).

5 My answer

public class Solution {
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    
        return construct(nums, 0, nums.length);
    }
    public TreeNode construct(int[] nums, int l, int r) {
    
        if (l == r)
            return null;
        int max_i = max(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }
    public int max(int[] nums, int l, int r) {
    
        int max_i = l;
        for (int i = l; i < r; i++) {
    
            if (nums[max_i] < nums[i])
                max_i = i;
        }
        return max_i;
    }
}