Same tree (checking whether given two trees are similar or not)


  • 0
    S
    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 isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
            return false;
        }
    };

  • 1
    S

    The first test, for "p==NULL && q==NULL" could just be p==q. This is true when both are null, as well as when both are the same non-null tree - in which case, returning true is much faster than recursing.

    It's easier to follow if your last test, for "p->val == q->val", is flipped to "p->val != q->val", along with flipping the returns. The lack of brackets and elses made me think at first that the last return was unreachable code. (Also, although out of scope here, putting the recursion in the last statement is better for tail-call optimization.)

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

  • 0
    S

    in the first step p points to diff address and q points to diff address. Only p->val & q->val will be same rit?


  • 0
    S

    if p != q, one of them might still be null, so p->val == q->val could be unavailable. If neither is null, then p->val and q->val might be the same, but you still have to check the children.


  • 0
    S

    I don't think any of the test cases have p==q, and even if they do it will always pass p->val==q->val. It's just much faster to avoid the recursion when p==q.


Log in to reply
 

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