当前位置：网站首页>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 从前序与中序遍历序列构造二叉树
边栏推荐
猜你喜欢
随机推荐
Top 10 free proxy IP software_Domestic static IP proxy software
又有大厂员工连续加班倒下/ 百度搜狗取消快照/ 马斯克生父不为他骄傲...今日更多新鲜事在此...
问题7：功能测试花瓶用例
【重构map】【重构filter】【重构Some】【重构reduce方法】【重构flat函数】
网络通信的过程
阿里大牛最新总结分享的高并发编程核心笔记（终极版），高并发系统架构场景一应俱全
【报错】import cv2 as cv ModuleNotFoundError: No module named ‘cv2
QT之Mysql驱动
JS每晚24:00更新某方法
LeetCode169：多数元素
问题5：发现缺陷怎么办？缺陷的类型有哪些？
【常见 error】Vivado 综合出现中断、失败、“PID not specified”
想成为网络安全技术爱好者（可能是黑客）的话，需要看什么书？
PAT乙级-B1009 说反话（20）
兆骑科创高层次人才引进平台，创新创业赛事活动路演
atrace和systrace的基本使用方法
devops-2：Jenkins的使用及Pipeline语法讲解
Huffman tree
Currency ATM: Solana Wallet Has Unknown Security Vulnerability, A Large Number Of Users' Digital Assets Are Stolen
正则表达式入门二(普通字符)