(第34天)645、最大二叉树

645、最大二叉树

题目描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
数组长度大于等于1

思路

常规思路：

1. 找到最大值和最大值的下标，根据这个值构建跟节点
2. 根据最大值下标分割数组为左子数组、右子数组
3. 根据左子数组递归的构造左子树、根据右子数组递归的构造右子树

代码实现思路：

1. 参数和返回值：传入数组；返回值为指向节点的指针。
2. 终止条件：因为数组长度大于等于1，所以当数组长度为1时，做完相关操作之后返回结果。
3. 递归逻辑：每次构造完根节点之后，按先序遍历顺序，先构造左子树、再构造右子树。

代码

/*** Definition for a binary tree node.* 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:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {// 数组长度>=1，所以直接创建新节点TreeNode* root = new TreeNode(0);// 终止条件:数组长度=1if (nums.size() == 1) {root -> val = nums[0];return root; }// 找到数组中最大值及其小标int maxValue = 0;int maxIndex = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] > maxValue) {maxIndex = i;maxValue = nums[i];}}// 构造根节点root -> val = maxValue;// 分割左子数组，递归构造左子树if (maxIndex > 0) {vector<int> newVec(nums.begin(), nums.begin() + maxIndex);root -> left = constructMaximumBinaryTree(newVec);}// 分割右子数组，递归构造右子树if (maxIndex < (nums.size() - 1)) {vector<int> newVec(nums.begin() + maxIndex + 1, nums.end());root -> right = constructMaximumBinaryTree(newVec);}return root;}
};