Easy to understand in C++ 0ms, using iteration and recursion respectively


  • 0
    V

    Solution 1:

     class Solution {
        public:
            bool isSameTree(TreeNode* p, TreeNode* q) {
                if (p == NULL && q == NULL) return true;
                if (p == NULL || q == NULL) return false;
                
                TreeNode *curp = NULL, *curq = NULL;
                
                queue<TreeNode *>qp;
                queue<TreeNode *>qq;
                qp.push(p);
                qq.push(q);
                
                while (!qp.empty() && !qq.empty())
                {
                    curp = qp.front();
                    qp.pop();
                    curq = qq.front();
                    qq.pop();
                    
                    if (curp == NULL && curq == NULL)
                        continue;
                    if (curp && curq)
                    {
                        if (curp->val != curq->val) return false;
                        qp.push(curp->left);
                        qp.push(curp->right);
                        qq.push(curq->left);
                        qq.push(curq->right);
                    }
                    else 
                        return false;
                }
                if (qp.empty() && qq.empty())
                    return true;
                    
                return false;
            }
        };
    

    Solution 2:

    class Solution {
    public:
        bool isSameTree(TreeNode* p, TreeNode* q) {
            if (p == NULL && q == NULL) return true;
            if (p == NULL || q == NULL) return false;
            if (p->val != q->val) return false;
            
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    };

  • 0
    H

    Do these two methods cost the same time? Which is faster?


  • 0
    V

    The run times are all 0ms,maybe the testcases are not enough.
    I think solution 1 is faster.


  • 0
    H

    Thanks! I find it a bit difficult to write an iterative one. But I heard iterative code is usually better.


  • 0
    V

    yeah.In general,recursion is fairly expensive compared to iteration(actually it depends on the language you use),but recursion is usually a lot cleaner than iteration.


Log in to reply
 

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