本文共 1611 字，大约阅读时间需要 5 分钟。

题目：654. 最大二叉树

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

二叉树的根是数组中的最大元素。

示例 ：

输入：[3,2,1,6,0,5]

6    /   \   3     5    \    /      2  0          \        1

提示：

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

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1. divide

   找出原始数组的最大值及其所在位置pos，将原始数组按照pos位置分为左边部分和右边部分。

2. conquer

   将pos位置的数组元素作为根节点root，然后递归地处理左边部分和右边部分，分别作为左子树left和右子树right。

3. combine

   将二叉树拼接起来，即root->left = left，root->right = right。
   return root

代码

/** * 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* constructMaximumBinaryTree(vector
   
    & nums) {
           return dfs(nums, 0, nums.size()-1);    }    TreeNode* dfs(vector
    
     & nums, int start, int end) {
           if (start > end) {
               return NULL;        }        int pos = maxPos(nums, start, end);        TreeNode* node = new TreeNode(nums[pos]);        TreeNode* left = dfs(nums, start, pos-1);        TreeNode* right = dfs(nums, pos+1, end);        node->left = left;        node->right = right;        return node;    }    int maxPos(vector
     
      & nums, int start, int end) {
           int max = nums[start];        int pos = start;        for (int i = start; i <= end; i++) {
               if (max < nums[i]) {
                   max = nums[i];                pos = i;            }        }        return pos;    }};