My 3 solutions in c++


  • 14
    J
    // recursive, it's trivial...
    vector<int> v;
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return v;
        inorderTraversal(root->left);
        v.push_back(root->val);
        inorderTraversal(root->right);
        return v;
    }
    
    
    // iterate, use stack
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        if(!root) return v;
        TreeNode* temp = root;
        stack<TreeNode*> s;
        while(true){
            while(temp){
                s.push(temp);
                temp = temp->left;
            }
            if(s.empty()) break;
            temp = s.top();
            s.pop();
            v.push_back(temp->val);
            temp = temp->right;
        }
        return v;
    }
    
    
    // iterate, morris traversal, without stack
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        if(!root) return v;
        TreeNode* temp = root, *prev;
        while(temp){
            if(!temp->left){
                v.push_back(temp->val);
                temp = temp->right;
            }else{
                prev = temp->left;
                while(prev->right&&(prev->right != temp))
                    prev = prev->right;
                if(!prev->right){
                    prev->right = temp;
                    temp = temp->left;
                }else{
                    v.push_back(temp->val);
                    prev->right = NULL;
                    temp = temp->right;
                }
            }
        }
    }

  • 0
    X

    Can you explain how the second solution works, please? I see you push the root to the stack first time go into the while, and set temp = temp->left. But you never used this temp before reassign it to s.top(). This code worked, but how could this be. I'm confused.


  • 0
    J

    while(temp){...} just goes to the left end, and pop S's top when it ends. S'top value is what we need at this iteration.Draw a tree may help you learn better.


Log in to reply
 

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