当前位置：网站首页>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 从前序与中序遍历序列构造二叉树
边栏推荐
猜你喜欢
![[The Beauty of Software Engineering - Column Notes] 36 | What exactly do DevOps engineers do?](/img/7e/405a32a67ba48342179bfbcb214f09.png)
[The Beauty of Software Engineering - Column Notes] 36 | What exactly do DevOps engineers do?
【R语言科研绘图】--- 柱状图
想成为网络安全技术爱好者（可能是黑客）的话，需要看什么书？
连亏四个月，赚不回电费，预制菜经销商恐成“韭菜”？
高性能创作本，日常修图剪辑选华硕无畏Pro15 2022完全足矣！
问题5：发现缺陷怎么办？缺陷的类型有哪些？
你没见过的《老友记》镜头，AI给补出来了｜ECCV 2022
树莓派 USB摄像头 实现网络监控（ MJPG-Streamer）
兔起鹘落全端涵盖,Go lang1.18入门精炼教程，由白丁入鸿儒，全平台(Sublime 4)Go lang开发环境搭建EP00
夜神浏览器fiddler抓包
随机推荐
Tao Te: Engine or baggage?
UE4 C disk cache solution
devops-2：Jenkins的使用及Pipeline语法讲解
PostgreSQL 每周新闻 2022-7-27
NFT盲盒挖矿DAO智能合约dapp系统开发详情
面试官都震惊，你这“网络基础”可以啊
php类的析构函数：__destruct
MMA安装及使用优化
高性能创作本，日常修图剪辑选华硕无畏Pro15 2022完全足矣！
2022年镇海夏令营组合数学和数论班 —— 数学作业 1
How to use redis
【常见 error】Vivado 综合出现中断、失败、“PID not specified”
基于.NET 6 的开源访客管理系统
自己悦表存心
GMapping principle analysis/easy to understand
交大医学院临床研究中心如何将 ModelWhale 应用于临床医生教学、研究丨数据科学 x 临床医学
不安装运行时运行.NET程序
程序员面试必备PHP基础面试题 – 第十九天
Clickhouse填坑记3：Left Join改Right Join导致统计结果错误
PHP中高级面试题 – 第一天