当前位置：网站首页>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 从前序与中序遍历序列构造二叉树
边栏推荐
猜你喜欢
162_Power Query is a custom function for quickly merging tables in a folder TableXlsxCsv_2.0
Jupyter Notebook 交互式编程 ＆ 低代码拖拽式编程 | 数据科学生态下的理想平台
手摸手带你完成智慧路灯构建及避坑【华为云至简致远】
测试基础整合-测试分类、软件质量模型、测试流程、测试用例、测试点划分方法、缺陷、例子
PostgreSQL V14中更好的SQL函数
南京一研究所回应招聘硕士保安：负责安全生产等，48人选1
网络中的交换机和路由器
![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]
网络通信的过程
PAT乙级-B1018 锤子剪刀布（20）
随机推荐
基于ModelArts的动漫头像自动生成丨【华为云至简致远】
ubiquant量化竞赛
6000 字＋，帮你搞懂互联网架构演变历程！
552个元宇宙App，70个搞社交，哪款真能交到朋友？
淘特：引擎还是包袱？
2022年镇海夏令营组合数学和数论班 —— 数学作业 1
【重构map】【重构filter】【重构Some】【重构reduce方法】【重构flat函数】
选择合适的 DevOps 工具，从理解 DevOps 开始
问题10：注册页面的易用性测试？
基于.NET 6 的开源访客管理系统
How to use redis
PHP中高级面试题 – 第一天
程序员面试必备PHP基础面试题 – 第十九天
教你如何获取微信公众号历史文章链接
【R语言科研绘图】--- 柱状图
网络通信的过程
STM32H743VIT6配置ADC为1M采样率
问题6：下拉框测试点
【问题】使用pip安装第三方库的时候遇到“timeout”的解决方法
在北极都可以穿短袖了，温度飙升至32.5℃