题目： 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?
递归解法（C++版本）：
/** * Definition for binary tree * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution{private:vector<int> result;public:vector<int> postorderTraversal(TreeNode *root){if (root){postorderTraversal(root->left);postorderTraversal(root->right);result.push_back(root->val);}return result;}};
二叉树非递归后序遍历思路： 二叉树非递归后续遍历是三种遍历中最难的，因为后续遍历最后访问根节点，操作中不好回溯到根节点，而前序遍历和中序遍历中，每次循环遍历中都是从根节点开始回溯很容易。 网上好些代码都是使用一个栈Stack进行操作的，代码不易懂，，读起来很吃力。 其实，可以使用两个Stack来进行二叉树非递归后续遍历。先访问根节点，入栈（A栈），记住根节点，出栈进入另外一个栈（B栈），然后该根节点左右子树入栈（A栈）。最后输出B栈的结果就OK了。
/** * 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;if (!root) return result;stack<TreeNode*> outputStack;stack<TreeNode*> middleStack;middleStack.push(root);TreeNode *node = nullptr;while (!middleStack.empty()){node = middleStack.top();middleStack.pop();outputStack.push(node);if (node->left){middleStack.push(node->left);}if (node->right){middleStack.push(node->right);}}while (!outputStack.empty()){result.push_back(outputStack.top()->val);outputStack.pop();}return result;}};
C#非递归参考代码：
/** * Definition for binary tree * public class TreeNode { *public int val; *public TreeNode left; *public TreeNode right; *public TreeNode(int x) { val = x; } * } */{public IList<int> PostorderTraversal(TreeNode root){IList<int> result = new List<int>();if (root == null) return result;Stack<TreeNode> outputStack = new Stack<TreeNode>();Stack<TreeNode> middleStack = new Stack<TreeNode>();middleStack.Push(root);TreeNode node = null;while (middleStack.Count != 0){node = middleStack.Pop();outputStack.Push(node);if (node.left != null) middleStack.Push(node.left);if (node.right != null) middleStack.Push(node.right);}while (outputStack.Count != 0){result.Add(outputStack.Pop().val);}return result;}}
成功是奋斗的结果，而奋斗是成功的必经之路。
