题目描述

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

1. 二叉树的根是数组中的最大元素。
2. 左子树是通过数组中最大值左边部分构造出的最大二叉树。
3. 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根结点。

样例

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

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

注意

• 给定的数组的大小在 [1, 1000] 之间。

算法

(递归) $O(n^2)$

1. 采用递归算法，假设 build(l, r) 表示对数组中 [l, r] 闭区间的部分构造二叉树；
2. 首先找出最大值及其所在位置 max_i，然后构造一个新的结点 rt，递归 build(l, max_i - 1) 和 build(max_i + 1, r) 分别作为 rt 的左右儿子，最后返回该结点 rt。

时间复杂度

• 最坏情况下，每次寻找的最大值都在当前区间的最左边，即数组是有序数组，这样就会有 n 层递归，总共需要 n + (n - 1) + (n - 2) + … + 1 次计算，所以时间复杂度是 $O(n^2)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* build(const vector<int>& nums, int l, int r) {
        if (l > r)
            return NULL;
        int max_num = nums[l], max_i = l;
        for (int i = l + 1; i <= r; i++)
            if (max_num < nums[i]) {
                max_num = nums[i];
                max_i = i;
            }
        TreeNode *rt = new TreeNode(max_num);
        rt -> left = build(nums, l, max_i - 1);
        rt -> right = build(nums, max_i + 1, r);
        return rt;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }
};