LeetCode 145 二叉树的后序遍历（非递归）

题目：

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

示例:

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路：

1、使用一个栈，先把二叉树的右孩子压入，再把左孩子压入。这样在输出时就满足后序要求（先左后右）。

2、当某个节点的左孩子或者右孩子都为NULL时，可以访问。此外记录当前节点p的上一个节点last，因为当p的左右孩子都已访问过时，轮到p被访问，设置last可标志p的左右孩子是否都被访问过了。即为 if((p->right == NULL && p->left == last) || p->right == last)

代码：

 /**
  * 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<int> ans;
         if(root == NULL)
             return ans;
         TreeNode* p = root;
         TreeNode* last;
         stack<TreeNode*> s;
         s.push(p);
         while(!s.empty())
         {
             p = s.top();
             if((p->left == NULL && p->right == NULL) || (p->right == NULL && p->left == last) || p->right == last)
             {
                 ans.push_back(p->val);
                 last = p;
                 s.pop();
             }
             else
             {
                 if(p->right)
                     s.push(p->right);
                 if(p->left)
                     s.push(p->left);
             }
         }
         return ans;
     }
 };