[leetcode]145-二叉树的后序遍历
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
给定一个二叉树，返回它的 后序 遍历。
例如输入[1,null,2,3] ：
1
\
2
/
3 输出：
[3,2,1]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
二、题解
参考：二叉树的后序遍历。
三、代码
3.1 通过栈+链表实现
/**
* 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) {
stack<TreeNode *> s;
list<TreeNode *> l;
vector<int> v;
TreeNode *p;
if (root == nullptr) {
return v;
}
s.push(root);
while (!s.empty()) {
p = s.top();
s.pop();
l.push_front(p);
if (p->left) {
s.push(p->left);
}
if (p->right) {
s.push(p->right);
}
}
while(!l.empty()) {
v.push_back(l.front()->val);
l.pop_front();
}
return v;
}
};
3.2 通过2次压栈实现
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
TreeNode *p;
vector<int> v;
stack<TreeNode *> st;
if (root == nullptr) {
return v;
}
st.push(root); st.push(root);
while (!st.empty()) {
p = st.top();
st.pop();
if (!st.empty() && st.top() == p) {
if (p->right) {
st.push(p->right); st.push(p->right);
}
if (p->left) {
st.push(p->left); st.push(p->left);
}
} else {
v.push_back(p->val);
}
}
return v;
}
};
