Morris traversal algo for preorder/inorder/postorder


  • 0
    T

    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;
        }
    };
    

Log in to reply
 

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