# The simplest Iterative & Morris solutions(postorder is "symmetric" to the preorder)

• 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());
}
}
``````

You can see the summary of all methods at here: http://blog.csdn.net/yc461515457/article/details/78082042

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