广州网站建设信科网络/网站流量统计查询

leetcode-654. 最大二叉树
给定一个不重复的整数数组 nums 。

最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。

class Solution {
public:TreeNode* constructMaximumBinaryTreeHelper(vector<int>& nums, int start, int end) {if (start > end)return NULL;// 找到 start~end的最大值int max_value = nums[start];int max_index = start;for(int i = start + 1; i <= end; i++) {if (max_value < nums[i]) {max_value = nums[i];max_index = i;}}TreeNode* root = new TreeNode(max_value);root->left = constructMaximumBinaryTreeHelper(nums, start, max_index - 1);root->right = constructMaximumBinaryTreeHelper(nums, max_index + 1, end);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return constructMaximumBinaryTreeHelper(nums, 0, nums.size()-1);}
};

时间复杂度：O(n^2)。constructMaximumBinaryTree 一共被调用 n 次。
每次递归寻找根节点时，需要遍历当前索引范围内所有元素找出最大值。
一般情况下，每次遍历的复杂度为 O(logn)，总复杂度为 O(nlogn)。
最坏的情况下，数组 nums 有序，总的复杂度为 O(n^2)

空间复杂度：O(n)。递归调用深度为 n。
平均情况下，长度为 n 的数组递归调用深度为 O(logn)

单调栈做法

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {stack<TreeNode*> s;int len = nums.size();TreeNode *curNode;for(int i = 0; i < len; i++) {curNode = new TreeNode(nums[i]);while (!s.empty() && (s.top())->val <= curNode->val) {TreeNode *tmp = s.top();s.pop();// 挂载问题，将弹出的栈顶元素挂在新的栈顶的右侧呢还是curNode的左侧呢if(!s.empty() && (s.top())->val <= curNode->val)(s.top())->right = tmp;elsecurNode->left = tmp;}s.push(curNode);}// 降序的处理// 比如栈中从底到顶部是 6 5 4 3 2 1// 则不断弹出一个，并让新的栈顶元素的right指向当前元素curNode = s.top();s.pop();while(!s.empty()) {(s.top())->right = curNode;curNode = s.top();s.pop();}return curNode;}
};

nums就是一个二叉树的中序序列
左-根-右