【力扣刷题】二叉树的统一迭代法-二叉树
其实针对三种遍历方式，使用迭代法是可以写出统一风格的代码！
重头戏来了，接下来介绍一下统一写法。
我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！ (opens new window)中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢？
- 方法一：就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法可以叫做
空指针标记法。 - 方法二：加一个
boolean值跟随每个节点，false(默认值) 表示需要为该节点和它的左右儿子安排在栈中的位次，true表示该节点的位次之前已经安排过了，可以收割节点了。 这种方法可以叫做boolean 标记法，样例代码见下文C++ 和 Python 的 boolean 标记法。 这种方法更容易理解，在面试中更容易写出来。
迭代法中序遍历
中序遍历（空指针标记法）代码如下：（详细注释）
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
if (node->right) st.push(node->right); // 添加右节点（空节点不入栈）
st.push(node); // 添加中节点
st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。
if (node->left) st.push(node->left); // 添加左节点（空节点不入栈）
} else { // 只有遇到空节点的时候，才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.top(); // 重新取出栈中元素
st.pop();
result.push_back(node->val); // 加入到结果集
}
}
return result;
}
};
中序遍历（boolean 标记法）：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<pair<TreeNode*, bool>> st;
if (root != nullptr)
st.push(make_pair(root, false)); // 多加一个参数，false 为默认值，含义见下文注释
while (!st.empty()) {
auto node = st.top().first;
auto visited = st.top().second; //多加一个 visited 参数，使“迭代统一写法”成为一件简单的事
st.pop();
if (visited) { // visited 为 True，表示该节点和两个儿子位次之前已经安排过了，现在可以收割节点了
result.push_back(node->val);
continue;
}
// visited 当前为 false, 表示初次访问本节点，此次访问的目的是“把自己和两个儿子在栈中安排好位次”。
// 中序遍历是'左中右'，右儿子最先入栈，最后出栈。
if (node->right)
st.push(make_pair(node->right, false));
// 把自己加回到栈中，位置居中。
// 同时，设置 visited 为 true，表示下次再访问本节点时，允许收割。
st.push(make_pair(node, true));
if (node->left)
st.push(make_pair(node->left, false)); // 左儿子最后入栈，最先出栈
}
return result;
}
};
此时我们再来看前序遍历代码。
迭代法前序遍历
迭代法前序遍历代码如下： (注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
st.push(node); // 中
st.push(NULL);
} else {
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
迭代法后序遍历
后续遍历代码如下： (注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
st.push(node); // 中
st.push(NULL);
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
} else {
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
迭代法后序遍历（boolean 标记法）：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<pair<TreeNode*, bool>> st;
if (root != nullptr)
st.push(make_pair(root, false)); // 多加一个参数，false 为默认值，含义见下文
while (!st.empty()) {
auto node = st.top().first;
auto visited = st.top().second; //多加一个 visited 参数，使“迭代统一写法”成为一件简单的事
st.pop();
if (visited) { // visited 为 True，表示该节点和两个儿子位次之前已经安排过了，现在可以收割节点了
result.push_back(node->val);
continue;
}
// visited 当前为 false, 表示初次访问本节点，此次访问的目的是“把自己和两个儿子在栈中安排好位次”。
// 后序遍历是'左右中'，节点自己最先入栈，最后出栈。
// 同时，设置 visited 为 true，表示下次再访问本节点时，允许收割。
st.push(make_pair(node, true));
if (node->right)
st.push(make_pair(node->right, false)); // 右儿子位置居中
if (node->left)
st.push(make_pair(node->left, false)); // 左儿子最后入栈，最先出栈
}
return result;
}
};版权声明：
作者：Zhang, Hongxing
链接：http://zhx.info/archives/623
来源：张鸿兴的学习历程
文章版权归作者所有，未经允许请勿转载。
THE END
二维码
文章目录
关闭