1. 제목

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] .
Note: Recursive solution is trivial, could you do it iteratively?

2. 분석

두 갈래 나무의 뒷부분을 두루 훑어보는 것은'좌우근'의 순서에 따라 노드를 두루 훑어보는 것이다. 이전 문장 [leetcode 먼저 훑어보는 것]과 마찬가지로 귀속법과 교체법이 있다.
귀속법은 간결하지만 효율은 낮다.
'후차적 반복'교체법의 프로그램은'선차적 반복'코드를 복용할 수 있다. 왜냐하면'선차적 반복'은 우리가'뿌리 좌우'의 교체판 코드를 실현하고 이를'뿌리 오른쪽 왼쪽'으로 바꾸어 얻은 결과의 재역순이 바로 후차적 반복'좌우 뿌리'의 결과이기 때문이다.
(선차적 반복법의 상세한 분석은 이전 문장 참조[leetcode 선차적 반복])

3. 코드

# 귀속법

<span style="font-size:18px;">/**
 * Definition for binary tree
 * 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) {
        vector<int> result,left_vec,right_vec;
        if(!root)  return result;
        left_vec=postorderTraversal(root->left);
        right_vec=postorderTraversal(root->right);
        for(vector<int>::iterator iter=left_vec.begin();iter!=left_vec.end();iter++)
             result.push_back(*iter);
        for(vector<int>::iterator iter1=right_vec.begin();iter1!=right_vec.end();iter1++)
             result.push_back(*iter1);
        result.push_back(root->val);
        return result;
    }
};</span>

# 교체법

<span style="font-size:18px;">class Solution {
public:
/*
    
 “ ”， “ ” ， “ ” 
 “ ” ， left、right ；
*/
    vector<int> postorderTraversal(TreeNode *root) {
        /* “ ” */
        vector<int> result;
        if(!root) return result;
        stack<TreeNode *> stk;
        stk.push(root);
        TreeNode *p=root;
        while(!stk.empty())
        {
            p=stk.top();
            stk.pop();
            result.push_back(p->val);
            
            if(p->left)   stk.push(p->left);
            if(p->right)  stk.push(p->right);
        }
        /* “ ”->“ ”*/
        for(auto i=result.begin(),j=result.end()-1;i<j;i++,j--)
            swap(*i,*j);
        return result;
    }
};</span>