LeetCode·每日一题·654.最大二叉树·递归·单调栈
2023-09-27 14:26:29 时间
链接:https://leetcode.cn/problems/maximum-binary-tree/solution/-by-xun-ge-v-qf9i/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目![](https://img-blog.csdnimg.cn/d0b448593c6a4713b915ab4cdb023c92.png)
示例![](https://img-blog.csdnimg.cn/e764bfd9b3bf4730aa1c97808b8575cc.png)
思路
解题思路
对于树的相关问题->用递归基本上都能解决
【递归构造】
题意需要构造一个最大二叉树,规则为:
- 创建一个根节点,其值为 nums 中的最大值。
- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
题目都告诉我们怎么递归了,直接根据题意递归构造即可
时间复杂度为O(n^2),使用单调栈优化为O(n)
【单调栈】
边遍历边构造二叉树的各个节点,使用一个递减的单调栈来存储元素,最后,栈底的元素就是整个二叉树的最大值,也就是根节点。
以 [3,2,1,6,0,5] 为例:
- 构造节点 3,入栈;
- 构造节点 2,它比栈顶元素 3 小,所以,它是 3 的右子节点,直接入栈;
- 构造节点 1,它比栈顶元素 2 小,所以,它是 2 的右子节点,直接入栈;
- 构造节点 6,它比栈顶元素 1 大,所以,1 是它的左子节点,弹出 1;同样地,栈顶元素 2 也比它小,弹出 2 并做为它的左子节点;把栈顶所有比它小的元素都弹出,最后弹出的是 3,所以,最终是 3 做为 6 的左子节点,并把 6 入栈;
- 构造节点 0,它比栈顶元素 6 小,所以,它是 6 的右子节点,直接入栈;
- 构造节点 5,它比栈顶元素 0 大,所以,0 是它的左子节点,弹出 0;接着比较,它比栈顶元素 6 小,所以,它是 6 的右子节点,入栈;
- 最后,栈中元素为 [6,5],栈底元素为 6,是最终的根节点;
代码
【递归构造】
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode * dfsCreateTree(int * nums, int left, int right)
{
if(left >= right)
{
return NULL;
}
int max = -1;
int index = left;
for(int i = left; i < right; i++)//寻找最大值,并保存下标
{
if(nums[i] > max)
{
index = i;
max = nums[i];
}
}
struct TreeNode * root = malloc(sizeof(struct TreeNode));//构造节点
root->val = max;//赋值
root->left = dfsCreateTree(nums, left, index);//递归构造左右节点
root->right = dfsCreateTree(nums, index+1, right);
return root;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
return dfsCreateTree(nums, 0, numsSize);//递归构造树
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/maximum-binary-tree/solution/-by-xun-ge-v-qf9i/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
【单调栈】
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
struct TreeNode * ans[numsSize];//定义单调栈
int top = -1;
for(int i = 0; i < numsSize; i++)//遍历所有节点
{
struct TreeNode * n = malloc(sizeof(struct TreeNode));//创建节点
n->val = nums[i];
n->left = NULL;
n->right = NULL;
while(top != -1 && ans[top]->val < n->val)//出栈并将栈顶元素赋为当前元素的左子节点
{
n->left = ans[top];
--top;
}
if(top != -1)//递减,是栈顶元素的右子节点
{
ans[top]->right = n;
}
ans[++top] = n;//入栈
}
return ans[0];
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/maximum-binary-tree/solution/-by-xun-ge-v-qf9i/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【LeetCode】二叉搜索树中第K小的元素 [M](二叉树遍历)
- LeetCode 102 Binary Tree Level Order Traversal(二叉树的层级顺序遍历)(*)
- LeetCode_回溯_BFS_中等_784.字母大小写全排列
- LeetCode_二叉平衡树_简单_110.平衡二叉树
- LeetCode_二叉树_中等_515.在每个树行中找最大值
- LeetCode_二叉树_简单_543.二叉树的直径
- LeetCode_排序_简单_88.合并两个有序数组
- LeetCode_二叉树_中等_113.路径总和 II
- LeetCode刷题(19)【简单】二叉树的前&&中&&后遍历(非递归)(C++)
- LeetCode·每日一题·1145.二叉树着色游戏·贪心
- LeetCode·每日一题·1832.判断句子是否为全字母句·模拟
- LeetCode·每日一题·1640.能否连接形成数组·模拟
- LeetCode·131.分割回文串·递归回溯
- LeetCode·101.对称二叉树·递归
- LeetCode·199·二叉树的右视图·层次遍历
- LeetCode·每日一题·919.完全二叉树插入器·层次遍历·BFS
- LeetCode·每日一题·814.二叉树剪枝·递归
- LeetCode·124.二叉树中的最大路径和·递归
- LeetCode-110. 平衡二叉树(java)
- [LeetCode] 244. Shortest Word Distance II 最短单词距离 II
- [LeetCode] 293. Flip Game 翻转游戏
- [LeetCode] 64. Minimum Path Sum 最小路径和
- #leetcode 637二叉树的层平均值
- 【LeetCode-Hot100-001】合并二叉树(617)