# Morris traversal algo for preorder/inorder/postorder

• ## postorder

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> rst;

TreeNode *ptr = root;
// c-r-l; pre-order, visit right node first
// reverse result
while (ptr) {
if (!ptr->right) {
rst.push_back(ptr->val);
ptr = ptr->left;
} else {
auto rch = ptr->right;
while (rch->left && rch->left != ptr) {
rch = rch->left;
}
if (!rch->left) {
rst.push_back(ptr->val);
rch->left = ptr, ptr = ptr->right;
}else {
rch->left = nullptr;
ptr = ptr->left;
}
}
}
reverse(rst.begin(), rst.end());
return rst;
}
};
``````

## inorder

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> rst;

TreeNode *ptr = root;
while (ptr) {
if (!ptr->left) {
rst.push_back(ptr->val);
ptr = ptr->right;
} else {
auto lch = ptr->left;
while (lch->right && lch->right != ptr) {
lch = lch->right;
}
if (!lch->right) {
lch->right = ptr;
ptr = ptr->left;
} else {
rst.push_back(ptr->val);
lch->right = nullptr;
ptr = ptr->right;
}
}
}
return rst;
}
};
``````

## preorder

``````class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> rst;

TreeNode *ptr = root;
while (ptr) {
if (!ptr->left) {
rst.push_back(ptr->val);
ptr = ptr->right;
} else {
TreeNode *lchild = ptr->left;
while (lchild->right && lchild->right != ptr) {
lchild = lchild->right;
}
if (!lchild->right) {
rst.push_back(ptr->val);
lchild->right = ptr;
ptr = ptr->left;
} else {
ptr = ptr->right;
lchild->right = nullptr;
}
}
}
return rst;
}
};
``````

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