题目描述

1. 最大二叉树
   给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

样例

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

算法

(DFS) $O(n)$

算法步骤如下:
1. 首先调用 dfs(nums, 0, n)，其中 n 是数组 nums 的长度。
2. 在索引范围 (l:r-1)(l:r−1) 内找到最大值的索引，将 nums[max_i]nums[max_i] 作为根节点。
3. 调用 dfs(nums, l, max_i) 创建根节点的左孩子。递归执行此操作，创建根节点的整个左子树。
4. 类似的，调用 dfs(nums, max_i + 1, r) 创建根节点的右子树。

时间复杂度 O(n)

Java 代码

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return null;
        }

        if (n == 1) {
            return new TreeNode(nums[0]);
        }

        return dfs(nums, 0, n - 1);
    }

    private TreeNode dfs(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        } else if (l == r) {
            return new TreeNode(nums[l]);
        } else {
            int idx = findMaxIndex(nums, l, r);
            TreeNode root = new TreeNode(nums[idx]);
            root.left = dfs(nums, l, idx - 1);
            root.right = dfs(nums, idx + 1, r);
            return root;
        }
    }

    private int findMaxIndex(int[] nums, int l, int r) {
        int idx = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] > nums[idx]) {
                idx = i;
            }
        }
        return idx;
    }
}