加油站建设专业网站,怎么做页眉,精英学校老师给学生做的网站,域名是什么 有什么用目录 645、最大二叉树题目描述思路代码 645、最大二叉树
题目描述
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点#xff0c;其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大… 目录 645、最大二叉树题目描述思路代码 645、最大二叉树
题目描述
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树 。 数组长度大于等于1
思路
常规思路
找到最大值和最大值的下标根据这个值构建跟节点根据最大值下标分割数组为左子数组、右子数组根据左子数组递归的构造左子树、根据右子数组递归的构造右子树
代码实现思路
参数和返回值传入数组返回值为指向节点的指针。终止条件因为数组长度大于等于1所以当数组长度为1时做完相关操作之后返回结果。递归逻辑每次构造完根节点之后按先序遍历顺序先构造左子树、再构造右子树。
代码
/*** 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(vectorint 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) {vectorint newVec(nums.begin(), nums.begin() maxIndex);root - left constructMaximumBinaryTree(newVec);}// 分割右子数组递归构造右子树if (maxIndex (nums.size() - 1)) {vectorint newVec(nums.begin() maxIndex 1, nums.end());root - right constructMaximumBinaryTree(newVec);}return root;}
};
