Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.
Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:
6
/ \
3 5
\ /
2 0
\
1
Note:
The size of the given array will be in the range [1,1000].
解法1:常规思路,递归
思路:用分治思想,递归.将nums以最大元素max为界切成两部分left和right.根的val为max,用left建立根的左子树,right建立根的右子树,如此递归进行.
/**
* 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* constructMaximumBinaryTree(vector<int>& nums) {
if (nums.size() == 0) { //若nums长度为0,递归终点
return NULL;
}
int max = nums[0]; //初始时假设max是0号元素
int max_idx = 0;
for (int i = 0; i < nums.size(); i++) { //找到nums中max及其下标
if (nums[i] > max) { //若找到新的max,更新
max = nums[i];
max_idx = i;
}
}
vector<int> left(nums.begin(), nums.begin()+max_idx); //nums左半部分复制到left
vector<int> right(nums.begin()+max_idx+1, nums.end()); //nums右半部分复制到right
//重点来了
TreeNode* root = new TreeNode(max); //根的val为max
root->left = constructMaximumBinaryTree(left); //递归处理根的左子树
root->right = constructMaximumBinaryTree(right); //递归处理根的右子树
return root; //返回根
}
};
有几个特别蠢的地方,调了半天才发现:
1.找nums最大值的时候,一开始令下标max_idx=-1,然后编译过了,一运行就爆内存,调试才发现如果max就是0号元素的话,max_idx=-1导致vector越界.
正确的做法是,max_idx不要取一个异常值为初值,因为max不一定能找到(不更新),而应该与max元素一一对应,例如一般假设初始时max就是nums[0],然后max_idx就应该是0.这样即使没找到新的max,即max=nums[0],那么max_idx也依然是正确的.
2.不要忘了return,特别是递归函数,return作为递归的出口,特别重要!
其实也不用这么死板,按照题目给出的函数头来写,这样递归被限制得太死(只有一个参数),不如用一个辅助函数:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1); // 辅助函数
}
//max_index denotes the index of the maximum number in range [left, right]
TreeNode* helper(vector<int>& nums, int left, int right){
if(left>right)return NULL;
int max_index = left;
for(int i = left; i<=right; i++){
if(nums[i] > nums[max_index])max_index = i;
}
TreeNode* root = new TreeNode(nums[max_index]);
root->left = helper(nums, left, max_index - 1);
root->right = helper(nums, max_index + 1, right);
return root;
}
解法2:用map,一次遍历加map插入,复杂度O(nlogn),比较难理解.
关键在于map是有序的*,每次插入后都会按key值重新排序,这样就理解为何要与begin,end比较.
另一个关键是为何处理完左子树后要把左边部分清除,因为是按从左到右的顺序读取nums的,因此当读取到nums[i]时,其左侧的元素都已确定并处理,若不清除的话,再读入nums[i]右侧的元素,插入map后就丢失元素位置信息了(map会重新排序,切记!),因此把左侧删掉后,map中剩下的就全是右侧元素了.
最后返回rbegin,即倒数第一个元素,map中key最大的值肯定是root,为何这样用呢?也很简单,因为end是不存储信息的,所以不能返回end
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
map<int, TreeNode*> q = { { nums[0], new TreeNode(nums[0]) } };
// 遍历nums,插入map
for (auto i = 1; i < nums.size(); ++i) {
auto it_b = q.insert({ nums[i], new TreeNode(nums[i]) });
if (it_b.first != q.begin()) { // 若插入的元素在map中不是第一个,插入left tree.
it_b.first->second->left = next(it_b.first, -1)->second;
q.erase(q.begin(), it_b.first); // 将左边部分清除
}
if (next(it_b.first, 1) != q.end()) // 若插入的元素的下一个不是end,则将其下一个插入right tree.
next(it_b.first, 1)->second->right = it_b.first->second;
}
return q.rbegin()->second; //返回map中最后一个(不是end)
}
