Iterator solution without stack O(1) space complexity and O(n) space complexity


  • 2
    H

    if current->left is not null, find current->left's right most node, point it to current node, and remove the current->left point

    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        TreeNode* now=root;
        while(now)
        {
            if(now->left)
            {
                TreeNode *p1=now->left;
                TreeNode *p=now->left;
                while(p->right)p=p->right;
                p->right=now;
                now->left=0;
                now=p1;
            }
            else
            {
                res.push_back(now->val);
                now=now->right;
            }
        }
        return res;
    }

Log in to reply
 

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