当前位置：网站首页>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 从前序与中序遍历序列构造二叉树
边栏推荐
- 利用华为云ECS服务器搭建安防视频监控平台【华为云至简致远】
- 图形学-粒子系统 (Particle System)
- 2022年镇海夏令营组合数学和数论班 —— 数学作业 1
- Clickhouse填坑记3：Left Join改Right Join导致统计结果错误
- The difference between servlet and jsp _ the difference between servlet and class
- 技术分享 | 接口自动化测试如何搞定 json 响应断言？
- Several methods of installing Mysql in Linux
- Use Typora+EasyBlogImageForTypora to write a blog and upload pictures quickly without a picture bed
- 教你如何获取微信公众号历史文章链接
- Detailed explanation of cloud hard disk EVS and how to use and avoid pits [HUAWEI CLOUD is simple and far]
猜你喜欢
![Detailed explanation of cloud hard disk EVS and how to use and avoid pits [HUAWEI CLOUD is simple and far]](/img/95/c05f184a6221fefaaa93beb9dccc33.png)
随机推荐
System learning Shell regular expressions
Leetcode 448. Find All Numbers Disappeared in an Array to Find All Disappeared in an Array of Numbers (simple)
我现在推荐用mamba替代conda
问题3：你提交的缺陷开发认为这不是BUG，怎么办？
SQL 不新增表 把一张表定义成两张
又有大厂员工连续加班倒下/ 百度搜狗取消快照/ 马斯克生父不为他骄傲...今日更多新鲜事在此...
UE4 C disk cache solution
想成为网络安全技术爱好者（可能是黑客）的话，需要看什么书？
Currency ATM: Solana Wallet Has Unknown Security Vulnerability, A Large Number Of Users' Digital Assets Are Stolen
如何把MapGIS的区文件转为ArcGIS的SHAPE面文件
Top 10 free proxy IP software_Domestic static IP proxy software
个人秋招记录——欢迎交流
MySQL性能优化的'4工具+10技巧'
ffplay视频播放原理分析
C语言将GLib库添加到CMake工程中
How to use matlab to implement the piecewise function "recommended collection"
Lecture 2 Software Life Cycle
取消转义字符(r)
阿里大牛最新总结分享的高并发编程核心笔记（终极版），高并发系统架构场景一应俱全
Jupyter Notebook 交互式编程 ＆ 低代码拖拽式编程 | 数据科学生态下的理想平台