# 0 ms Clear C++ solutions --- iterative, recursive, Morris traversal (3 different solutions!)

• Hi, this is a fundamental and yet classic problem. I share my three solutions here:

1. Iterative solution using stack --- `O(n)` time and `O(n)` space;
2. Recursive solution --- `O(n)` time and `O(n)` space (considering the spaces of function call stack);
3. Morris traversal --- `O(n)` time and `O(1)` space!!!

Iterative solution using stack:

``````vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
stack<TreeNode*> toVisit;
TreeNode* curNode = root;
TreeNode* lastNode = NULL;
while (curNode || !toVisit.empty()) {
if (curNode) {
toVisit.push(curNode);
curNode = curNode -> left;
}
else {
TreeNode* topNode = toVisit.top();
if (topNode -> right && lastNode != topNode -> right)
curNode = topNode -> right;
else {
nodes.push_back(topNode -> val);
lastNode = topNode;
toVisit.pop();
}
}
}
return nodes;
}
``````

Recursive solution:

``````void postorder(TreeNode* root, vector<int>& nodes) {
if (!root) return;
postorder(root -> left, nodes);
postorder(root -> right, nodes);
nodes.push_back(root -> val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
postorder(root, nodes);
return nodes;
}
``````

Morris traversal:

``````void reverseNodes(TreeNode* start, TreeNode* end) {
if (start == end) return;
TreeNode* x = start;
TreeNode* y = start -> right;
TreeNode* z;
while (x != end) {
z = y -> right;
y -> right = x;
x = y;
y = z;
}
}
void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
reverseNodes(start, end);
TreeNode* node = end;
while (true) {
nodes.push_back(node -> val);
if (node == start) break;
node = node -> right;
}
reverseNodes(end, start);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
TreeNode* dump = new TreeNode(0);
dump -> left = root;
TreeNode* curNode = dump;
while (curNode) {
if (curNode -> left) {
TreeNode* predecessor = curNode -> left;
while (predecessor -> right && predecessor -> right != curNode)
predecessor = predecessor -> right;
if (!(predecessor -> right)) {
predecessor -> right = curNode;
curNode = curNode -> left;
}
else {
reverseAddNodes(curNode -> left, predecessor, nodes);
predecessor -> right = NULL;
curNode = curNode -> right;
}
}
else curNode = curNode -> right;
}
return nodes;
}``````

• ``````public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack();
List<Integer> result = new ArrayList();
TreeNode curr = root;
TreeNode lastVisited = null;
while(!s.isEmpty() || curr != null){
if(curr != null){
s.push(curr);
curr = curr.left;
}
else{
TreeNode peekNode = s.peek();
if(peekNode.right != null && peekNode != lastVisited){
curr = peekNode.right;
}
else{
lastVisited = s.pop();
}
}
}
return result;
}
``````

Basicly, I use the same idea as your iterative approach, but I got TLE. I don't know why. Can you help? Thank you very much.

• `if(peekNode.right != null && peekNode != lastVisited){` should be

`if(peekNode.right != null && peekNode.right != lastVisited){`.

• Oh, thank you so much. Big help~

• @jianchao.li.fighter Another solution : ) we can iterate the tree in preorder but little different: root --> right --> left . Than reverse it:

``````vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if(root == NULL) return result;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()) {
auto cur = stk.top();
result.push_back(cur->val);
stk.pop();
if(cur->left) stk.push(cur->left);
if(cur->right) stk.push(cur->right);
}
reverse(result.begin(), result.end());
return result;
}
``````

• Anyone know how to traverse in post order using Morris traversal in Java?

• This post is deleted!

• @wangxinbo I'm sorry man, I don't even realize that, it must be a operational error. I have no impression that I downvote your reply. Now I change it. So sorry about that.

• @jianchao-li-fighter
I have noticed that the postorder traversal is left-right symmetric to the preorder traversal!
Thus, when conducting postorder traversal, you first visit parent node, then the right child tree, last the left child tree.
However, to get a right answer, you need to inverse the result!
I have tested the code on OJ, they are accepted!

Iterative Traversal

``````vector<int> postorderTraversal(TreeNode* root) {
vector<int> nums;
stack<TreeNode* > stnode;
while (root || !stnode.empty()) {
if (!root) {
root = stnode.top();
stnode.pop();
}
nums.push_back(root->val);
if (root->left) stnode.push(root->left);
root = root->right;
}
return vector<int>(nums.rbegin(), nums.rend())
}
``````

Morris Traversal

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nums;
TreeNode* cur = nullptr;

while (root) {
if (root->right) {
cur = root->right;
while (cur->left && cur->left != root) {
cur = cur->left;
}
if (cur->left == root) {
cur->left = nullptr;
root = root->left;
} else {
nums.push_back(root->val);
cur->left = root;
root = root->right;
}
} else {
nums.push_back(root->val);
root = root->left;
}
}
return vector<int>(nums.rbegin(), nums.rend());
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.