【LeetCodeゼロブラシから】Binary Tree Postorder Traversal

タイトル:
Given a binary tree, return the postorder traversal of its nodes' values.
For example: Given binary tree  {1,#,2,3} ,

   1
    \
     2
    /
   3

return  [3,2,1] .
回答:
ツリーの非再帰バージョンは、後続の遍歴です.二叉木の様々な遍歴の非再帰バージョンの難易度は異なり、大体、前順>中順>後順である.
後順遍歴の実現の他の考え方はここを参考にすることができる:転送ゲート
ここでは簡単な方法を紹介します.前序が最も実現しやすいため、後序遍歴中の「左右根」を「根右左」の逆序バージョンと見なすことができますか?「根右左」は前序遍歴と同じ実現原理を持っているのだろうか.答えは肯定的だ.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> postorder; 
        vector<int> ans; ans.clear();
        
        if(root == NULL)    return ans;
        
        TreeNode* tmp = root;
        postorder.push(root);
        
        while(!postorder.empty()){
            
            //     vector   stack   
            ans.push_back(postorder.top()->val);
            tmp = postorder.top();
            postorder.pop();
            
            //        ，  reverse
            if(tmp->left)   postorder.push(tmp->left);
            if(tmp->right)  postorder.push(tmp->right);
        }
        reverse(ans.begin(), ans.end());
        
        return ans;
    }
};