题目概述

https://leetcode-cn.com/problems/maximum-binary-tree/

题目分析

  1. 二叉树的根是数组 nums 中的最大元素（写一个函数获取当前数组中的最大index）

  2. 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。

    右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

    写一个函数用来返回

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package com.code.note.test;

import com.code.note.tree.TreeNode;
import com.code.note.util.BTreePrinter;

public class Solution {

    public TreeNode constructMaximumBinaryTree(Integer[] nums) {
        return helper(nums, 0, nums.length-1);
    }

    public TreeNode helper(Integer[] nums, int start, int end) {
        if (start > end) return null;
        int index = findMaxIndex(nums, start, end);
        TreeNode t = new TreeNode(nums[index]);
        t.left = helper(nums, start, index - 1);
        t.right = helper(nums, index + 1, end);
        return t;
    }

    public int findMaxIndex(Integer[] arr, int start, int end) {
        int bigIndex = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] > arr[bigIndex]) {
                bigIndex = i;
            }
        }
        return bigIndex;
    }

    public static void main(String[] args) {

        Solution s = new Solution();
        Integer[] arr1 = {3, 2, 1, 6, 0, 5};

        TreeNode root = s.constructMaximumBinaryTree(arr1);
        BTreePrinter.printNode(root);

    }
}