给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点,其值为 nums 中的最大值
- 递归地在最大值 左边 的 子数组前缀上 构建左子树
- 递归地在最大值 右边 的 子数组后缀上 构建右子树
1. 暴力分治构造
暴力在于每次递归都要找一次最大值
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return construct(nums, 0, nums.size() - 1);
}
//分治构造子树
TreeNode* construct(const vector<int>& nums, int left, int right) {
if (left > right) return nullptr;//边界条件,相等时还需要构建单个节点
int best = left;//记录最大值位置
for (int i = left + 1; i <= right; ++i)
if (nums[i] > nums[best])
best = i;
TreeNode* node = new TreeNode(nums[best]);
node->left = construct(nums, left, best - 1);
node->right = construct(nums, best + 1, right);
return node;
}
};
2. 顺序更新树
实现最大数的插入值方法,便可以顺序建树
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* root = nullptr;
for(int val:nums)
root = insertIntoMaxTree(root,val);
return root;
}
//一个一个插入更新
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if(!root) return new TreeNode(val);
if(root->val<val)//如果该值大于根节点值,该值作为根节点,原树作为左子树
return new TreeNode(val,root,nullptr);
else //放到右子树递归构造
root->right = insertIntoMaxTree(root->right,val);
return root;
}
};
3. 单调栈
暴力构造的时候,会有重复的遍历找最值,可以通过单调栈一次遍历
本质上是找每个元素左侧和右侧第一个比它大的元素
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
int n = nums.size();
stack<int> s;//单调栈
vector<int> left(n, -1), right(n, -1);//记录每个元素左右侧第一个更大元素位置
vector<TreeNode*> tree(n);//将值转换成树节点
for (int i = 0; i < n; ++i) {//从左往右遍历
tree[i] = new TreeNode(nums[i]);//新建节点
while (!s.empty() && nums[i] > nums[s.top()]) {//单调栈消消乐
right[s.top()] = i;
s.pop();
}//该值就是他们的右侧第一个更大值
if (!s.empty()) left[i] = s.top();//同时得到该元素左侧第一个更大值
s.push(i);//入栈
}
TreeNode* root = nullptr;
//构建各节点的链接关系
for (int i = 0; i < n; ++i) {//从左往右遍历
if (left[i] == -1 && right[i] == -1) //左右均无更大值,该值作为根节点
root = tree[i];
//右侧无更大值(必然作为右节点存在),或都有更大值的情况下,左侧更小
else if (right[i] == -1 || (left[i] != -1 && nums[left[i]] < nums[right[i]]))
tree[left[i]]->right = tree[i];//作为左侧第一个更大元素的右节点
else
tree[right[i]]->left = tree[i];//作为右侧第一个更大元素的左节点
}
return root;
}
};
标签:right,TreeNode,最大,nums,int,二叉树,root,LeetCode,left
From: https://www.cnblogs.com/929code/p/16607013.html