dreamwearver做网站,公司网站优化怎么做,淘宝服务商,wordpress 多网址题目
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下#xff1a;
二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树
二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树并且输出这个树的根节点。
思路和之前的构造树一样分成左右区间子树递归
/*** 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* traversal (vectorint nums, int numsBegin, int numsEnd) {if (numsBegin numsEnd) return NULL;//寻找最大数值int maxVal nums[numsBegin];int delimiterIndexnumsBegin;for(int inumsBegin;inumsEnd;i){if(nums[i]maxVal){delimiterIndex i;maxValnums[delimiterIndex];}}TreeNode* root new TreeNode(maxVal);//如果是叶子结点返回结点if (numsEnd - numsBegin 1) return root;// for (delimiterIndex numsBegin; delimiterIndex numsEnd; delimiterIndex) {// if (nums[delimiterIndex] rootValue) break;// }// 切割nums数组// 左区间左闭右开[leftInorderBegin, leftInorderEnd)int leftorderBegin numsBegin;int leftorderEnd delimiterIndex;// 右区间左闭右开[rightInorderBegin, rightInorderEnd)int rightorderBegin delimiterIndex 1;int rightorderEnd numsEnd;root-left traversal(nums, leftorderBegin, leftorderEnd);root-right traversal(nums, rightorderBegin, rightorderEnd);return root;}TreeNode* constructMaximumBinaryTree(vectorint nums) {if(nums.size() 0) return NULL;return traversal(nums,0,nums.size());}
};
