Why my c++ code doesn't work? Is the problem in the recursion?


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

    And can someone explain it to me that how recursion works?


  • 1
    V

    While loop should be removed, recursion checks all the nodes values, you are not handling the case when p->val and q->val are equal, no need to consider the equality of left and right pointers just check for the current node's value whether they are equal or not, no need to check for true == isSameTree( ) operator && checks whether the returned value is true or not.

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

  • 0
    S
    This post is deleted!

  • 0
    Q

    while loop is not necessary (and bad), but doesn't matter here, since "while" is a looped "if" and you basically "return" from every case.
    The p->val == q->val is handled implicitly already, since you do "if (p->val != q->val) return false;"
    Now, there real problem is "testing left and right child's val". While p and q are not NULL, their child can be, since you didn't test that. And you cannot do NULL->val. Your code gets run time error.

    If you remove that piece, you code will be accepted, although is still not as clean and clear as Vivek.bits' .


Log in to reply
 

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