最大二叉樹

力扣題目鏈接

題目描述

給定一個不重復的整數數組 nums 。 最大二叉樹 可以用下面的算法從 nums 遞歸地構建:

創建一個根節點，其值為 nums 中的最大值。
遞歸地在最大值 左邊 的 子數組前綴上 構建左子樹。
遞歸地在最大值 右邊 的 子數組后綴上 構建右子樹。
返回 nums 構建的 最大二叉樹 。

解題思路

很簡單粗暴的思路，直接每次遞歸的時候遍歷一遍數組，找出最大的值作為節點的值，然后分割左右數組重復該操作。
者做法雖然效率不高，但是思路上比較簡單。

題解

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() == 0){return NULL;}else if(nums.size() == 1){return new TreeNode(nums[0]);}int maxp = 0;for(int i = 1; i < nums.size(); i++){if(nums[i] > nums[maxp]){maxp = i;}}TreeNode* root = new TreeNode(nums[maxp]);if(maxp != 0){vector<int> left(nums.begin(), nums.begin() + maxp);root->left = constructMaximumBinaryTree(left);}if(maxp != nums.size() - 1){vector<int> right(nums.begin() + maxp + 1, nums.end());root->right = constructMaximumBinaryTree(right);}return root;}
};