text: # 145. Binary Tree Postorder Traversal
  
  **<font color=red>难度:Hard<font>**
  
  ## 刷题内容
  > 原题连接
  
  * https://leetcode.com/problems/binary-tree-postorder-traversal/
  
  > 内容描述
  
  ```
  Given a binary tree, return the postorder traversal of its nodes' values.
  
  Example:
  
  Input: [1,null,2,3]
     1
      \
       2
      /
     3
  
  Output: [3,2,1]
  Follow up: Recursive solution is trivial, could you do it iteratively?
  ```
  
  > 思路1
  ******- 时间复杂度: O(N)******- 空间复杂度: O(1)******
  
  后序遍历二叉树，先判断左子树存不存在，在判断右子树存不存在，最后添加root->val即可。
  
  ```cpp
  /**
   * 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:
      void travel(TreeNode* root,vector<int>& v)
      {
          if(!root)
              return;
          if(root ->left)
              travel(root ->left,v);   
          if(root ->right)
              travel(root ->right,v);
          v.push_back(root ->val);
      }
      vector<int> postorderTraversal(TreeNode* root) {
          vector<int> v;
          travel(root,v);
          return v;
      }
  };
  ```
  > 思路2
  ******- 时间复杂度: O(N)******- 空间复杂度: O(N)******
  
  题目中提到了不用递归用遍历的方式去解决这个问题。那么我们就需要用栈去储存元素，这时候我们还需要一个辅助栈来标记这个元素是否应该 pop。
  
  ```cpp
  /**
   * 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) {
              vector<TreeNode*> v;
          vector<int> ans;
          vector<int> count1;
          if(root)
          {
              v.push_back(root);
              count1.push_back(0);
          }
          while(v.size())
          {
              int index = v.size();
              if(!count1[index - 1] && v[index -1] ->left)
              {
                  count1[index - 1] = 1;
                  v.push_back(v[index - 1] ->left);
                  count1.push_back(0);
              }
              else if(count1[index - 1] != 2 && v[index - 1] ->right)
              {
                  count1[index - 1] = 2;
                  v.push_back(v[index - 1] ->right);
                  count1.push_back(0);
              }
              else
              {
                  ans.push_back(v[index - 1] ->val);
                  count1.pop_back();
                  v.pop_back();
              }
          }
          return ans;
      }
  };
  ```