二叉树的后序遍历(非递归)-蒲公英云

二叉树的后序遍历(非递归)

二叉树的后序遍历

题目描述 :

后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [3,2,1]

来源：力扣（LeetCode）
OJ链接

相关:
二叉树的前序遍历(非递归)
二叉树的中序遍历(非递归)
二叉树的层序遍历(非递归)

分析 :

非递归的后序遍历就比较复杂了, 需要两个栈来实现, 一个栈来入栈左右孩子, 另一个栈作为入栈的节点的标记, 每一个节点都对应一个标记, 标记什么呢? 标记这个结点是否还有左孩子, 也就是意味着弹出栈顶到这个节点时是否出栈或是访问其右节点, 具体来看代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    stack<bool> tag;
    vector<int> res;
    TreeNode* cur = root;
    while (cur||!st.empty()) {
        for (; cur; cur = cur->left) {
        st.push(cur);
        tag.push(false);
        }
        while (!st.empty() && tag.top()) {
        res.push_back(st.top()->val);
        st.pop();
        tag.pop();
        }
        if (!st.empty()) {
        tag.top() = true;
        cur = st.top()->right;
        }
        else {
        break;
        }
    }
        return res;
    }
};