心似已灰之木
身如不系之舟
隔了十天没写过博客了，今天的每日一题给了道二叉树中序遍历，想想这不是送积分吗。。。
题目中写了可以尝试非递归版本，于是我想了想，网上大部分关于二叉树非递归遍历的版本好像其实只是模拟二叉树遍历而已，并没有用栈模拟函数的递归调用。
于是突然就想杠一波，实现用栈模拟递归遍历二叉树。
这里几个知识点，就是函数调用本身就是栈伸缩的过程：
- 发生函数调用则栈伸展
- 函数调用完毕则栈收缩
- 函数需要的参数和局部变量会存储在对应的栈帧上（当然也可以在寄存器里）
- 函数执行过程就是CPU从RIP/EIP寄存器取指令的过程
回忆一下，递归实现中序遍历的代码是什么？
void get(int val);
void dfs(TreeNode *root) {
if (root == nullptr) return ;
dfs(root->left);
get(root->val);
dfs(root->right);
}
很显然，针对这个递归遍历，栈帧的设计可以是这样的：
--------
TreeNode* root // 子函数
--------
--------
TreeNode* root // 父函数
--------
...
也就是每一层栈，存储的就是函数参数TreeNode* root。
这时候有个问题，在函数调用的过程中，是通过RIP寄存器记录下一条要执行的指令的地址，以递归实现中序遍历，过程大概是这样（当然实际执行的粒度是汇编/二进制语句，这里粗略简化成一行代码）：
- 执行指令
call dfs(root->left)前，会将RIP寄存器指向函数中要执行的下一条语句get(root->val) - RIP实际记录的是指令地址，且本身RIP会被后面的执行逻辑覆盖，这里面涉及一些函数调用约定的知识，就不再细讲了
- 也就是在调用子函数之前，会有一种方式记录返回到父函数后，后续要执行逻辑的位置
为了模拟这个”记录返回到父函数后，后续要执行逻辑的位置“，栈帧结构修改如下：
--------
int process
TreeNode* root // 子函数
--------
--------
int process
TreeNode* root // 父函数
--------
...
这里的process就用来记录当前栈帧已经被执行过的过程。
把递归实现中序遍历拆分成4个过程：
- 判断
TreeNode* root是否为空指针 call dfs(root->left)，这个过程就表示新的栈帧进入到栈里- 取
root->val值 call dfs(root->right)，这个过程就表示新的栈帧进入到栈里
结束这四个过程，当前栈帧就应该从栈中弹出。
当然实际代码编写过程中是不用这么啰嗦的，我们可以把1-2都归为一个过程，所以栈模拟函数递归中序遍历的非递归版本就。。。出来了：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<pair<TreeNode *, int>> st;
vector<int> ans;
if (root)
st.push(make_pair(root, 0));
while (!st.empty()) {
auto &item = st.top();
if (item.first == nullptr) {
st.pop();
continue;
}
if (item.second == 0) {
item.second++;
st.push(make_pair(item.first->left, 0));
} else if (item.second == 1) {
ans.push_back(item.first->val);
item.second++;
} else if (item.second == 2) {
st.push(make_pair(item.first->right, 0));
item.second++;
} else st.pop();
}
return ans;
}
};
改成前序遍历只需要把过程顺序换一下就好了。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<pair<TreeNode *, int>> st;
vector<int> ans;
if (root)
st.push(make_pair(root, 0));
while (!st.empty()) {
auto &item = st.top();
if (item.first == nullptr) {
st.pop();
continue;
}
if (item.second == 0) {
ans.push_back(item.first->val);
item.second++;
} else if (item.second == 1) {
item.second++;
st.push(make_pair(item.first->left, 0));
} else if (item.second == 2) {
st.push(make_pair(item.first->right, 0));
item.second++;
} else st.pop();
}
return ans;
}
};
后续遍历同理：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<pair<TreeNode *, int>> st;
vector<int> ans;
if (root)
st.push(make_pair(root, 0));
while (!st.empty()) {
auto &item = st.top();
if (item.first == nullptr) {
st.pop();
continue;
}
if (item.second == 0) {
item.second++;
st.push(make_pair(item.first->left, 0));
} else if (item.second == 1) {
st.push(make_pair(item.first->right, 0));
item.second++;
} else if (item.second == 2) {
ans.push_back(item.first->val);
item.second++;
} else st.pop();
}
return ans;
}
};
代码也不长2333。
