// Binary Tree Postorder Traversal // stack class Solution { public: vector postorderTraversal(TreeNode *p) { vector a; stack s; for(;;) { while (p) { s.push(p); p = p->left; } while (! s.empty() && s.top()->right == p) { p = s.top(); s.pop(); a.push_back(p->val); } if (s.empty()) break; p = s.top()->right; } return a; } }; // Morris post-order traversal class Solution { void reverse_right_chain(TreeNode *x, TreeNode *y) { TreeNode *p = x, *q = x->right, *right; while (p != y) { right = q->right; q->right = p; p = q; q = right; } } public: vector postorderTraversal(TreeNode* root) { vector ret; TreeNode aux(0), *p = &aux; aux.left = root; aux.right = NULL; while (p) { TreeNode *q = p->left; if (q) { while (q->right && q->right != p) q = q->right; if (q->right == p) { reverse_right_chain(p->left, q); for (TreeNode *r = q; ; r = r->right) { ret.push_back(r->val); if (r == p->left) break; } reverse_right_chain(q, p->left); q->right = NULL; } else { q->right = p; p = p->left; continue; } } p = p->right; } return ret; } };