题目要求
给定一个二叉树，返回后序遍历的结果。
注：尝试用递归和迭代两种方法。
类似题目：
解答：leetcode 94. Binary Tree Inorder Traversal (二叉树的中序遍历，递归法，非递归法)
解答： leetcode 144. Binary Tree Preorder Traversal(二叉树的前序遍历，递归法，非递归法)
示例
/* Example */
Input: [1,null,2,3]1\2/3Output: [3,2,1]
解题思路
什么是后序遍历？
后：指的是根节点出现的位置，以一个简单的树型结构举例，对树中的每个节点，在遍历的时候都按照先遍历左孩子结点，中间遍历右孩子节点，最后遍历根结点。
(结果为: 3-1-2)。
2/ \3 1
以此类推，我们可以知道
前序遍历是：先遍历根节点，中间是左孩子，最后是右孩子节点。（结果为：2-3-1）
中序遍历是先遍历左孩子节点，中间遍历根节点，最后是右孩子。（结果为：3-2-1）
怎么实现后序遍历？
1、递归
递归方法是解决树类问题中常用的方法，易于理解，在解答本题的时候，我们根据上面讲的后序遍历方法，能写出如下的代码：
/*vector <int> postorder; // 保存节点的值。 */
vector<int> postorderTraversal(TreeNode* root) {
postorderTraversal(root->left);postorderTraversal(root->right);postorder.push_back(root->val);}
递归主要代码（c++）
/*** 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) {
if(root != NULL) // 如果当前节点非空，那么执行递归。{
postorderTraversal(root->left);postorderTraversal(root->right);postorder.push_back(root->val);}return postorder; }
private:vector<int>postorder;
};
2、 迭代法（非递归）
由于递归实现树的遍历非常简单，所以在面试的时候，面试官通常会不让我们用递归来做，特别是针对后序遍历的非递归实现是重点考察点的题目，这里我们介绍一下非递归实现树的遍历。需要借助 栈 这个数据结构来实现。
而且，二叉树的后序遍历和其前序，中序遍历相比，更为复杂（hard级别的难度），我们一步步来看。
我们来想一下，后序遍历的要点是根节点出现在开始的位置（先左后右最后根）。
这里边的难点就是，我们要知道当前结点是左孩子，还是右孩子，如果是左孩子，那么还要继续右孩子的遍历，如果是右孩子，那么下一步就是保存根节点的值
这里给出两种解法，第一种使用双栈，一个栈可以实现 中-> 右-> 左, 然后再用一个栈逆转即可，理解起来比较容易。第二个是用一个pre指针，记录前一个节点，
非递归主要代码–双栈实现（c++）
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {
if(!root)return {
};stack<TreeNode*>s1;stack<TreeNode*>s2;vector<int>ans;s1.push(root);while(!s1.empty()) //先用一个栈来存放节点{
TreeNode* cur = s1.top();s1.pop();// 取出节点s2.push(cur); // 倒叙阶段放入s2中 先放入1，再放入2，最后放入3if(cur->left) s1.push(cur->left);if(cur->right) s1.push(cur->right);}while(!s2.empty()) // 输出阶段{
TreeNode* tmp = s2.top();s2.pop();ans.push_back(tmp->val);}return ans;}
};
基于双栈的python实现
class Solution(object):def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return Nones1 = []s2 = []res = []s1.append(root)while s1:cur = s1.pop(-1)s2.append(cur)if cur.left:s1.append(cur.left)if cur.right:s1.append(cur.right)while s2:tmp = s2.pop(-1)res.append(tmp.val)return res非递归主要代码–基于pre实现（c++）
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {
if(!root)return {
};stack<TreeNode*>s;s.push(root);TreeNode* pre = NULL;vector<int>ans;while(!s.empty()){
TreeNode* cur = s.top();if((cur->left==NULL && cur->right==NULL)||(pre!=NULL && (pre==cur->left||pre==cur->right))) //叶子结点或者中间节点记录{
ans.push_back(cur->val);s.pop();pre = cur; // 关键！！}else{
if(cur->right) s.push(cur->right);if(cur->left) s.push(cur->left);}}return ans;}
};
总结一下
1、不同于二叉树的前序中序遍历，在非递归后续遍历的时候，我们需要知道前一个节点是什么，因此判断是不是取出还是继续遍历。
2、个人感觉双栈的解法比较容易理解，可以先从双栈看起。
3. 特别推荐前序遍历和中序遍历一起来学习，实现过程相似。
leetcode 94. Binary Tree Inorder Traversal (二叉树的中序遍历，递归法，非递归法)
leetcode 144. Binary Tree Preorder Traversal(二叉树的前序遍历，递归法，非递归法)