当前位置：网站首页>leetcode-105 从前序与中序遍历序列构造二叉树-使用栈代替递归
leetcode-105 从前序与中序遍历序列构造二叉树-使用栈代替递归
2022-08-03 14:54:00 【Silent_Blue_Sky】
使用递归法这个是很容易实现的（当然前提是你对二叉树遍历顺序熟悉）
本文重点是采用栈的方式来解决问题， 毕竟据说递归能实现的解法用栈都能实现
步骤一： 观察递归法需要知道的状态
一般常见写法
这个写法可能没那么好观察出状态
class Solution {
public:
TreeNode* buildTreeHelper(vector<int>& preorder, int l1, int h1, vector<int>& inorder, int l2, int h2) {
if (l1 > h1) {
return nullptr;
}
int val = preorder[l1];
int i = l2;
for (; i <= h2; i++) {
if (inorder[i] == val) {
break;
}
}
int lsz = i - l2;
auto root = new TreeNode(val);
root->left = buildTreeHelper(preorder, l1 + 1, l1 + lsz, inorder, l2, i - 1);
root->right= buildTreeHelper(preorder, l1 + lsz + 1, h1, inorder, i + 1, h2);
return root;
}
// 最一般的递归构造
TreeNode* buildTree_recursion(vector<int>& preorder, vector<int>& inorder) {
return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
}
那么如果换成下面的写法
void buildTreeHelper(vector<int>& preorder, int l1, int h1, vector<int>& inorder, int l2, int h2, TreeNode* &father, TreeNode* TreeNode::*child) {
if (l1 > h1) {
return;
}
int val = preorder[l1];
auto node = new TreeNode(val);
if (nullptr == father) {
father = node;
} else {
father->*child = node;
}
int i = l2;
for (; i <= h2; i++) {
if (inorder[i] == val) {
break;
}
}
int lsz = i - l2;
buildTreeHelper(preorder, l1 + 1, l1 + lsz, inorder, l2, i - 1, node, &TreeNode::left);
buildTreeHelper(preorder, l1 + lsz + 1, h1, inorder, i + 1, h2, node, &TreeNode::right);
}
// 最一般的递归构造
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode* root = nullptr;
buildTreeHelper2(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, root, nullptr);
return root;
}
知道栈必须保存的状态
1. preorder 全局可以获取
2. l1
3. h14. inorder 全局可以获取
4. l2
5. h2
6. father
7. child 或者用tag代替
定义栈保存结构
可用结构一
struct OneItemTag {
int l1, h1, l2, h2;
int tag;
TreeNode* father;
OneItemTag(int l1, int h1, int l2, int h2, int tag, TreeNode* fa = nullptr):l1(l1), h1(h1), l2(l2), h2(h2), tag(tag), father(fa){
}
};
可用结构二
struct OneItem {
int l1, h1, l2, h2;
TreeNode* TreeNode::*child;
TreeNode* father;
OneItem(int l1, int h1, int l2, int h2, TreeNode* TreeNode:: *child, TreeNode* fa = nullptr):l1(l1), h1(h1), l2(l2), h2(h2), child(child), father(fa){
}
};
逻辑处理
/* * @lc app=leetcode.cn id=105 lang=cpp * * [105] 从前序与中序遍历序列构造二叉树 */
// @lc code=start
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
public:
TreeNode* buildTreeHelper(vector<int>& preorder, int l1, int h1, vector<int>& inorder, int l2, int h2) {
if (l1 > h1) {
return nullptr;
}
int val = preorder[l1];
int i = l2;
for (; i <= h2; i++) {
if (inorder[i] == val) {
break;
}
}
int lsz = i - l2;
auto root = new TreeNode(val);
root->left = buildTreeHelper(preorder, l1 + 1, l1 + lsz, inorder, l2, i - 1);
root->right= buildTreeHelper(preorder, l1 + lsz + 1, h1, inorder, i + 1, h2);
return root;
}
// 最一般的递归构造
TreeNode* buildTree_recursion(vector<int>& preorder, vector<int>& inorder) {
return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
struct OneItemTag {
int l1, h1, l2, h2;
int tag;
TreeNode* father;
OneItemTag(int l1, int h1, int l2, int h2, int tag, TreeNode* fa = nullptr):l1(l1), h1(h1), l2(l2), h2(h2), tag(tag), father(fa){
}
};
TreeNode* buildTreeTag(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) {
return nullptr;
}
stack<OneItemTag> st;
TreeNode* root = nullptr;
st.push(OneItemTag(0, (int)preorder.size() - 1, 0, (int)inorder.size() - 1, 0, nullptr));
while (!st.empty()) {
auto one = st.top();
st.pop();
int l1 = one.l1;
int h1 = one.h1;
int l2 = one.l2;
int h2 = one.h2;
int tag = one.tag;
TreeNode* father = one.father;
if (l1 > h1) {
continue;
}
if (l1 == h1) {
auto node = new TreeNode(preorder[l1]);
if (father == nullptr) {
root = node;
} else {
if (-1 == tag) {
father->left = node;
} else if (1 == tag) {
father->right = node;
}
}
continue;
}
int val = preorder[l1];
int i = l2;
for (; i <= h2; i++) {
if (inorder[i] == val) {
break;
}
}
int lsz = i - l2;
auto node = new TreeNode(val);
if (father == nullptr) {
root = node;
} else {
if (-1 == tag) {
father->left = node;
} else if (1 == tag) {
father->right = node;
}
}
st.push(OneItemTag(l1 + 1, l1 + lsz, l2, i - 1, -1, node));
st.push(OneItemTag(l1 + lsz + 1, h1, i + 1, h2, 1, node));
}
return root;
}
struct OneItem {
int l1, h1, l2, h2;
TreeNode* TreeNode::*child;
TreeNode* father;
OneItem(int l1, int h1, int l2, int h2, TreeNode* TreeNode:: *child, TreeNode* fa = nullptr):l1(l1), h1(h1), l2(l2), h2(h2), child(child), father(fa){
}
};
// 递归的都能用栈， 用栈场所
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) {
return nullptr;
}
stack<OneItem> st;
TreeNode* root = nullptr;
st.push(OneItem(0, (int)preorder.size() - 1, 0, (int)inorder.size() - 1, nullptr, nullptr));
while (!st.empty()) {
auto one = st.top();
st.pop();
int l1 = one.l1;
int h1 = one.h1;
int l2 = one.l2;
int h2 = one.h2;
auto child = one.child;
TreeNode* father = one.father;
if (l1 > h1) {
continue;
}
if (l1 == h1) {
auto node = new TreeNode(preorder[l1]);
if (father == nullptr) {
root = node;
} else {
father->*child = node;
}
continue;
}
int val = preorder[l1];
int i = l2;
for (; i <= h2; i++) {
if (inorder[i] == val) {
break;
}
}
int lsz = i - l2;
auto node = new TreeNode(val);
if (father == nullptr) {
root = node;
} else {
father->*child = node;
}
st.push(OneItem(l1 + 1, l1 + lsz, l2, i - 1, &TreeNode::left, node));
st.push(OneItem(l1 + lsz + 1, h1, i + 1, h2, &TreeNode::right, node));
}
return root;
}
};
// @lc code=end
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
leetcode-105 从前序与中序遍历序列构造二叉树
边栏推荐
- liunx服务器nohup不输出日志文件的方法
- Detailed explanation of cloud hard disk EVS and how to use and avoid pits [HUAWEI CLOUD is simple and far]
- 2022年镇海夏令营组合数学和数论班 —— 数学作业 1
- A high-performance creation book, ASUS Dreadnought Pro15 2022 is completely enough for daily photo editing and editing!
- LeetCode169：多数元素
- 想成为网络安全技术爱好者（可能是黑客）的话，需要看什么书？
- SwiftUI SQLite教程之了解如何在 SwiftUI 中使用 SQLite 数据库并执行 CRUD 操作（教程含源码）
- 基于.NET 6 的开源访客管理系统
- The difference between servlet and jsp _ the difference between servlet and class
- 【常见 error】Vivado 综合出现中断、失败、“PID not specified”
猜你喜欢
彻底搞懂云桌面配置及实践踩坑【华为云至简致远】
DeepLink在转转的实践
【问题】torch和torchvision对应版本
雷克萨斯lm的安全性如何，通过两个角度来聊这个话题
Jupyter Notebook 交互式编程 ＆ 低代码拖拽式编程 | 数据科学生态下的理想平台
![Detailed explanation of cloud hard disk EVS and how to use and avoid pits [HUAWEI CLOUD is simple and far]](/img/95/c05f184a6221fefaaa93beb9dccc33.png)
Detailed explanation of cloud hard disk EVS and how to use and avoid pits [HUAWEI CLOUD is simple and far]
Mysql 生成排序序号
如何把MapGIS的区文件转为ArcGIS的SHAPE面文件
UE4 C disk cache solution
淘特：引擎还是包袱？
随机推荐
Day2：面试必考题目
Use Typora+EasyBlogImageForTypora to write a blog and upload pictures quickly without a picture bed
R7 6800H+RTX3050+120Hz 2.8K OLED screen, Intrepid Pro15 2022 pre-sale
个人秋招记录——欢迎交流
gocron定时任务管理系统的安装与运行
又有大厂员工连续加班倒下/ 百度搜狗取消快照/ 马斯克生父不为他骄傲...今日更多新鲜事在此...
手摸手带你完成智慧路灯构建及避坑【华为云至简致远】
兆骑科创高层次人才引进平台，创新创业赛事活动路演
苹果开发「AI 建筑师」GAUDI：根据文本生成超逼真 3D 场景！
程序员面试必备PHP基础面试题 – 第十九天
在北极都可以穿短袖了，温度飙升至32.5℃
彻底搞懂云桌面配置及实践踩坑【华为云至简致远】
PAT乙级-B1011 A+B 和 C（15）
简单理解try catch和try finally
Tao Te: Engine or baggage?
淘特：引擎还是包袱？
【指针内功修炼】函数指针 + 函数指针数组 + 回调函数（二）
雷克萨斯lm的安全性如何，通过两个角度来聊这个话题
liunx服务器遇到SYN_SENT洪水攻击
跨桌面端之组件化实践