LeetCode 145. Binary Tree Postorder Traversal二叉树的后序遍历 (C++)
题目：
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的左子树，访问根节点1的右子树，再访问根节点1。
1: node1->left, node1->right, node1->val;
node1左子树为空，我们继续访问node1的右子树。
2: node2->left, node2->right, node2->val, node1->val;
node2左子树为空，继续访问右子树
3: node3->left, node3->right, node3->val, node2->val, node1->val;
node3左右子树都为空，结果就是[3, 2, 1]。
用栈模拟的话，递归顺序是node1，之后是node2，node3，实际上也就是根节点，右子树，左子树，根节点我们可以直接输出，左右子树节点压入栈时候要注意，先将左子树压入，再将右子树节点压入，这样可以保证下次迭代执行栈内节点时，先执行右子树。
最后得到的结果要反转一下。
程序：
//递归 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> res; help(res, root); return res; } void help(vector<int> &vec, TreeNode* root){ if(root == nullptr) return; help(vec, root->left); help(vec, root->right); vec.push_back(root->val); } };
//迭代 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { if(root == nullptr) return {}; vector<int> res; stack<TreeNode*> s; s.push(root); while(!s.empty()){ root = s.top(); s.pop(); res.push_back(root->val); if(root->left) s.push(root->left); if(root->right) s.push(root->right); } reverse(res.begin(), res.end()); return res; } };