LeetCode145. 二叉树的后序遍历
文章目录
1.问题
2.思路
（1）什么是后序遍历
（2）递归
和前序中序思路一样，只是将根结点放到最后访问
（3）迭代思路
a.改造先序遍历
b.仿造中根遍历
中根遍历：1.从根节点自上而下沿着左侧分支下行，并把沿途结点压栈，直到最深的结点（无左孩子）。
2.沿着左侧通道，自下而上弹栈，依次访问沿途各结点及其右子树。
如下图所示：
而后序遍历面临一个问题： 弹栈后，不能马上访问p，而是要先访问p的右子树，然后访问p。所以需要以某种方式保存p。
策略1：不谈栈p，而是只取栈顶元素值。
策略2：允许结点多次进出栈，即弹栈p后让其马上再进栈。
策略1
策略2：
在栈元素里设置一个二元组，维护一个标号i，i代表当前结点进/出栈次数。 二叉树中任一结点p都要进栈三次，出栈三次。
第一次出栈是为遍历p的左子树。
第二次出战是为遍历p的右子树。
第三次出栈是为了访问p。
运行实例
伪代码
3.代码实现
（1）递归
class Solution
{
public:
void posOrder(TreeNode*cur,vector<int>& vec)
{
if(cur == NULL)return;
posOrder(cur->left,vec);//左
posOrder(cur->right,vec);//右
vec.push_back(cur->val);//根
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
posOrder(root, result);
return result;
}
};
（2）迭代
a.改造先序遍历
class Slution{
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int> result;
if(root == NULL) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.pop();
st.pop();
result.push_nack(node->val);
if(node->left st.push(node->left));//相对于前序遍历这里做一下更改
if(node->right) st.push(node->right);//空节点不入栈
}
reverse(result.begin(),result.end());//反转下结果就是左右中的顺序
return result;
}
};
b.策略1
class Solution{
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int> result;
TreeNode* p = root;
TreeNode* pre = NULL;// pre是p的后根前驱，即在p之前访问的结点
while(1){
while(p!=NULL){
st.push(p);
p = p->left;
}
if(st.empty()) return result;
p = st.top();
if(p!=NULL){
if( p->right == NULL||pre == p->right)
{
p = st.top();st.pop();
result.push_back(p->val);
pre = p; p = NULL;
}
else p = p->right;
}
}
}
};
b.策略2
使用STL：
class Solution{
public:
vector<int> postorderTraversal(TreeNode* root) {
int flag[512];
int top = 0;//top指向即将放入元素的位置 这确实不好使 因为stl里没有改变top
stack<TreeNode*>st;
vector<int> result;
flag[top] = 1;
st.push(root);
top++;
while(!st.empty()){
TreeNode* p = st.top();
st.pop();//出栈
top--;
if(flag[top] == 1){
flag[top] = 2; st.push(p); top++;
if(p!= NULL && p->left != NULL)
{
flag[top] = 1;
st.push(p->left);
top++;
}
}
else if(flag[top] == 2)
{
flag[top] = 3; st.push(p);top++;
if(p!=NULL && p->right != NULL){
flag[top] = 1;
st.push(p->right);
top++;
}
}
else if(p!=NULL && flag[top] == 3)
result.push_back(p->val);
}
return result;
}
};
注意！top得另外维护一下！stl里可没有int top这种东西！
不使用STL：
int flag[512];
int top = 0;//top指向即将放入元素的位置
class stac{
public:
void InitStack(){
top = 0;
}
void Push(TreeNode *p){
stack[top++] = p;
}
TreeNode* Pop(){
top--;
return stack[top];
}
bool empty() {
if (top == 0)return true;
return false;
}
TreeNode* Top( ){
return stack[top-1];
}
private:
TreeNode *stack[512];
};
class Solution{
public:
vector<int> postorderTraversal(TreeNode* root) {
stac st;
st.InitStack();
vector<int> result;
flag[top] = 1;
st.Push(root);
while(!st.empty()){
TreeNode* p = st.Pop();//出栈
if(flag[top] == 1){
flag[top] = 2; st.Push(p);
if(p!= NULL && p->left != NULL)
{
flag[top] = 1;
st.Push(p->left);
}
}
else if(flag[top] == 2)
{
flag[top] = 3; st.Push(p);
if(p!=NULL && p->right != NULL){
flag[top] = 1;
st.Push(p->right);
}
}
else if(p!=NULL && flag[top] == 3)
{
result.push_back(p->val);
}
else
continue;
}
return result;
}
};