每日算法题

654题

class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { //找最大值和最大值的下标作为根 TreeNode*node=new TreeNode(0); if(nums.size()==1) { node->val=nums[0]; return node; //终止条件 } //找到最大值 int maxvalue=0; int maxvalueindex=0; for(int i=0;i<nums.size();i++) { if(nums[i]>maxvalue) { maxvalue=nums[i]; maxvalueindex=i;//下标 } } node->val=maxvalue;//根节点 //左子树 if(maxvalueindex>0) { vector<int> newVec(nums.begin(),nums.begin()+maxvalueindex); node->left=constructMaximumBinaryTree(newVec); } if(maxvalueindex<(nums.size()-1)) { vector<int> newVec(nums.begin()+maxvalueindex+1,nums.end()); node->right=constructMaximumBinaryTree(newVec); } return node; } };

目标是找最大值，然后当根节点，

思路：找最大值和最大值的下标，切割左右子树，就这样接着遍历，

但是开数组造成空间效率低，所以给另一种简洁代码

class Solution { private: // 在左闭右开区间[left, right)，构造二叉树 TreeNode* traversal(vector<int>& nums, int left, int right) { if (left >= right) return nullptr; // 分割点下标：maxValueIndex int maxValueIndex = left; for (int i = left + 1; i < right; ++i) { if (nums[i] > nums[maxValueIndex]) maxValueIndex = i; } TreeNode* root = new TreeNode(nums[maxValueIndex]); // 左闭右开：[left, maxValueIndex) root->left = traversal(nums, left, maxValueIndex); // 左闭右开：[maxValueIndex + 1, right) root->right = traversal(nums, maxValueIndex + 1, right); return root; } public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return traversal(nums, 0, nums.size()); } };

这个也是进行切割，不过利用传值切割代替开数组，效率高