[145]二叉树的后序遍历

//给定一个二叉树，返回它的 后序 遍历。 
//
// 示例: 
//
// 输入: [1,null,2,3]  
//   1
//    \
//     2
//    /
//   3 
//
//输出: [3,2,1] 
//
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
// Related Topics 栈 树 
// 👍 534 👎 0

/*
* 145 二叉树的后序遍历
* 2021-03-04 19:32:32
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};

        stack<pair<TreeNode*,bool>> stk;
        auto ptr = root;
        vector<int> ans;

        while(stk.size() || ptr){
            if(ptr){
                // get into left
                stk.push(make_pair(ptr, false));
                ptr = ptr->left;
            }else{
                auto now = stk.top();stk.pop();
                if(now.second){ // back from right
                    ans.push_back(now.first->val);
                }else{ // go to right
                    stk.push(make_pair(now.first, true));
                    ptr = now.first->right;
                }
            }
        }
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)