# 145. Binary Tree Postorder Traversal

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?

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if (!root) return {};
vector<int> res;
stack<TreeNode*> s{{root}};
while (!s.empty()) {
TreeNode *t = s.top();
if ((!t->left && !t->right) || t->left == head || t->right == head) {
res.push_back(t->val);
s.pop();
} else {
if (t->right) s.push(t->right);
if (t->left) s.push(t->left);
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if (!root) return {};
vector<int> res;
stack<TreeNode*> s{{root}};
while (!s.empty()) {
TreeNode *t = s.top(); s.pop();
res.insert(res.begin(), t->val);
if (t->left) s.push(t->left);
if (t->right) s.push(t->right);
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
res.insert(res.begin(), p->val);
p = p->right;
} else {
TreeNode *t = s.top(); s.pop();
p = t->left;
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if (!root) return {};
vector<int> res;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode *t = s1.top(); s1.pop();
s2.push(t);
if (t->left) s1.push(t->left);
if (t->right) s1.push(t->right);
}
while (!s2.empty()) {
res.push_back(s2.top()->val); s2.pop();
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/145

Binary Tree Preorder Traversal

Binary Tree Inorder Traversal

Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-postorder-traversal/

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45803/java-solution-using-two-stacks

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/preorder-inorder-and-postorder-iteratively-summarization

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45621/preorder-inorder-and-postorder-traversal-iterative-java-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation