1、题目描述

. - 力扣（LeetCode）

其实就是给定了一个所谓"最大二叉树"的规则，让我们去构建二叉树。

以 nums = [3,2,1,6,0,5] 为例，规则如下：

(1)找出其中的最大值6将其作为根节点，6前面的是左子树、6后面的是右子树。

(2)左子树数组为[3,2,1]按照同样的规则，其中最大的是3作为左子树的根节点、前面构建左子树的左子树、后面构建左子树的右子树。

(3)以此类推即可。

2、分析

    构造二叉树类的题目看起来都差不多。
    遍历顺序：凡是构造二叉树类的题目我们都要用前序遍历(中左右)。
    —— 先构造根节点然后递归的构造左右子树。

    (1)递归函数的样式如下。返回值返回的是TreeNode*、入参是数组。
    TreeNode* buildTrree(vector<int>& nums)
    (2)递归函数内部首先就是退出条件。
    无非是数组为空(空节点)或数组只能构造一个节点(叶子节点)。
    (3)接下来就是明确根节点的值并构造根节点。
    (4)根节点构造完毕后就是获取构造左右子树的素材数组
    (5)然后就是递归的构造左右子树，并将结果直接返回给当前根节点。
    root->left = buildTree();
    root->left = buildTree();

class Solution {
public://1.首先明确函数的入参及返回值TreeNode* constructMaximumBinaryTree(vector<int>& nums) {//2.函数内首先确定退出条件(nums长度为0返回空、nums长度为1返回目标节点)if(nums.size() == 0) return NULL;if(nums.size() == 1) return new TreeNode(nums[0]);//3.找出最大值构建根节点，然后递归的构建左右子树//3.1.找出最大值并构建根节点int max_index = 0, max_num = nums[0];for(int i = 1; i < nums.size(); i++){if(nums[i] > max_num){max_index = i;max_num = nums[i];}}TreeNode* root = new TreeNode(nums[max_index]);//3.2.构建左、右子树的数组lnums、rnumsvector<int> lnums(nums.begin(), nums.begin()+max_index);vector<int> rnums(nums.begin()+max_index+1, nums.end());//3.3.递归地构建左右子树root->left = constructMaximumBinaryTree(lnums);root->right = constructMaximumBinaryTree(rnums);return root;}void levelorder(TreeNode* root){queue<TreeNode*> que;que.push(root);while(!que.empty()){int level_size = que.size();for(int i = 0; i < level_size; i++){TreeNode* tmp = que.front();cout << tmp->val << ",";que.pop();if(tmp->left) que.push(tmp->left);if(tmp->right) que.push(tmp->right);}cout << endl;}}
};

3、实现代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <math.h>using namespace std;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(): val(0), left(nullptr), right(nullptr){}TreeNode(int x): val(x), left(nullptr), right(nullptr){}TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right){}
};class Solution {
public://1.首先明确函数的入参及返回值TreeNode* constructMaximumBinaryTree(vector<int>& nums) {//2.函数内首先确定退出条件(nums长度为0返回空、nums长度为1返回目标节点)if(nums.size() == 0) return NULL;if(nums.size() == 1) return new TreeNode(nums[0]);//3.找出最大值构建根节点，然后递归的构建左右子树//3.1.找出最大值并构建根节点int max_index = 0, max_num = nums[0];for(int i = 1; i < nums.size(); i++){if(nums[i] > max_num){max_index = i;max_num = nums[i];}}TreeNode* root = new TreeNode(nums[max_index]);//3.2.构建左、右子树的数组lnums、rnumsvector<int> lnums(nums.begin(), nums.begin()+max_index);vector<int> rnums(nums.begin()+max_index+1, nums.end());//3.3.递归地构建左右子树root->left = constructMaximumBinaryTree(lnums);root->right = constructMaximumBinaryTree(rnums);return root;}void levelorder(TreeNode* root){queue<TreeNode*> que;que.push(root);while(!que.empty()){int level_size = que.size();for(int i = 0; i < level_size; i++){TreeNode* tmp = que.front();cout << tmp->val << ",";que.pop();if(tmp->left) que.push(tmp->left);if(tmp->right) que.push(tmp->right);}cout << endl;}}
};int main()
{Solution s1;vector<int> nums{3,2,1,6,0,5};TreeNode* root = s1.constructMaximumBinaryTree(nums);s1.levelorder(root);}