题干
给定一个二叉树的根节点 root
,返回 它的 前中后序 遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[1,3,2]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
解题思路
上一次我们使用了迭代法来实现前中后序遍历,但是每一种遍历的访问和处理顺序不同,导致代码书写风格不同,不像是递归法,实现了其中的一种遍历方式,其他两种只要稍稍改一下节点顺序就可以了。
但其实针对三种遍历方式,使用迭代法是可以写出统一风格的代码的。下面我们就来实现一下。
我们以中序遍历为例,我们之前提到使用栈的话,无法同时解决访问节点(遍历节点)和处理节点(将元素放进结果集)顺序不一致的情况。
事实上,访问这个操作是持续进行的,而处理节点则是需要时机的,在中序遍历中,时机就是遍历到叶子节点。关键是如何把处理节点和访问节点都用栈的逻辑解决,之前的迭代法中,用到了指针来帮助访问和处理。
我们将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。其实每一个节点都是需要处理的,只是时机未到,而做的标记则可以帮助我们判断处理节点的时机。
如何标记呢,就是将要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
添加左节点和右节点的时候,空节点不入栈,这样遇到空指针即代表遇到叶子节点,到了处理节点的时机。
中序遍历
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{
//把标记NULL弹出
st.pop();
//取出节点放入结果数组
node = st.top();
st.pop();
result.push_back(node->val);
}
}
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;
}
};
这样此时我们写出了统一风格的迭代法,不用在纠结于前序写出来了,中序写不出来的情况了。