Please help me on my DFS iteration method


  • 0
    N

    My DFS iteration method (the first one) costs 6 ms. Another DFS iteration method (the second one) costs 3ms. Anybody can explain why they are different? Many thanks!

    bool isSymmetric(TreeNode* root) {
            if(root == NULL)    return true;
            stack<TreeNode*> l, r;
            l.push(root->left);   r.push(root->right);
            
            while(!l.empty() || !r.empty()){
                if(l.empty() || r.empty())  return false;
                TreeNode* lp = l.top();
                TreeNode* rp = r.top();
                l.pop(); r.pop();
                if(!lp && !rp)  continue;
                if(!lp || !rp)  return false;
                if(lp->val != rp->val)  return false;
                else{
                    l.push(lp->right);   l.push(lp->left);
                    r.push(rp->left);  r.push(rp->right);
                }
            }
            return true;
        }
    
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        stack<TreeNode*> sl, sr;
        sl.push(root);
        sr.push(root);
        TreeNode * lp = root->left, *rp = root->right;
        while(lp || ! sl.empty() || rp || !sl.empty()){
            if((!lp && rp) || (lp && !rp)) return false;
            if(lp && rp){
                if(lp->val != rp->val) return false;
                sl.push(lp);
                sr.push(rp);
                lp = lp->left;
                rp = rp->right;
            }else{
                lp = sl.top()->right;
                rp = sr.top()->left;
                sl.pop();
                sr.pop();
            }
        }
        return true;
    }
    

Log in to reply
 

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