题目描述：
给定一个二叉树，返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？算法思想：递归形式无须赘述。非递归形式需要说明一下，后序遍历的顺序是左右根，因此设置一个stack来存放根左右，然后出栈顺序就是根右左，得到的结果放入到一个vector中，最后将vector逆置即可得到非递归的后序遍历写法 //递归形式
/** * 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 traverse(TreeNode* root,vector<int> &res){ if(root==NULL) return ; traverse(root->left,res); traverse(root->right,res); res.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root) { if(root==NULL) return {}; vector<int> res; traverse(root,res); return res; } };//非递归形式
/** * 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) return {}; stack<TreeNode*> s; vector<int> res; s.push(root); while(!s.empty()){ TreeNode* now=s.top(); s.pop(); res.push_back(now->val); if(now->left){ s.push(now->left); } if(now->right){ s.push(now->right); } } reverse(res.begin(),res.end()); return res; } };