C++ Morris Traversal solution with comments


  • 0
    Y
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> reval;
            TreeNode dummy(0);
            dummy.left = root;
            root = & dummy;
            while(root){
                if(root->left){
                    TreeNode *prede(root->left);
                    while(prede->right && prede->right!=root){
                        prede = prede->right;
                    }
                    if(prede->right!=root){
                        //first access current node, root
                        prede->right = root;
                        //go to left branch
                        root = root->left;
                    } else {
                        //second time access current node, root
                        //reset back
                        prede->right = nullptr;
                        
                        // Add elements from left child to predecessor
                        reversePopulate(reval,root->left,prede);
                        
                        // Go to right branch if it has right child, otherwise will go to successor 
                        root = root->right;
                    }
                } else {
                    // No left branch
                    // go to right branch if it has right child, otherwise go to successor
                    root = root->right;
                }
            }
            return reval;
        }
    private:
        void reversePopulate(vector<int> & reval, const TreeNode *left_child, const TreeNode *prede){
            if(!left_child) return;
            if(left_child != prede){
                reversePopulate(reval,left_child->right,prede);
            }
            reval.push_back(left_child->val);
        }
    };
    

Log in to reply
 

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