Correcting this traversal while capturing already visited in single variable


  • 0
    L

    This code uses an extra variable to avoid revisits to the same node. If you are popping back from a left node then it should not visit it again. If you are poping back from right node, it should not do so again.

    What could be a better way to capture this and correct the code

    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode *root) {
            
            stack<TreeNode*> st;
            vector<int> ret;
            
            if(root)
                st.push(root);
            
            TreeNode *cur=NULL, *done=NULL;
            
            while( !st.empty())
            {
                cur = st.top();
                
                if(cur->left && done != cur->left)
                {
                    st.push(cur->left);
                }
                else
                {
                    ret.push_back(cur->val);
                    st.pop();
                    
                    if( !done  || cur != done->right )
                        done = cur;
                    
                    if( cur->right )
                        st.push(cur->right);
    
                }
            }
            return ret;
            
        }
    };

Log in to reply
 

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