My 4ms C++ iterative solutions


  • 1
    X
    //version 1
        vector<int> inorderTraversal(TreeNode *root) {
            stack<TreeNode*> tstack;
            vector<int> vals;
            if(root==NULL)  return vals;
            tstack.push(root);
            while(!tstack.empty()) {
                while(root) {
                    if(tstack.top()!=root)  tstack.push(root);
                    root=root->left;
                }
                root=tstack.top();
                vals.push_back(root->val);
                tstack.pop();
                if(root->right) {
                    tstack.push(root->right);
                }
                root=root->right;
            }
            return vals;
        }
    
    
    //version 2: simpler
        vector<int> inorderTraversal(TreeNode *root) {
            stack<TreeNode*> stack;
            vector<int> vals;
            while(!stack.empty() or root) {
                while(root) {
                    stack.push(root);
                    root=root->left;
                }
                root=stack.top();
                stack.pop();
                vals.push_back(root->val);
                root=root->right;
            }
            return vals;
        }

Log in to reply
 

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