C++ fast, non-recursive solution with detailed explanation (using BFS)


  • 0
    H

    Conditions needed to pass: Same structure AND each node has the same value.

    Same structure: using queue, pushing and popping order is left leave then right.
    +++ fail if: 2 queues have different size OR one of 2 leaves being examined is empty

    Same value: proceed if structure test passed
    +++ fail if: 2 leaves have different values

    bool isSameTree(TreeNode* p, TreeNode* q){
            //if 2 trees are empty then they are identical
    	if(p == NULL && q == NULL) return true; 
    
    	queue<TreeNode*> P, Q;
    	P.push(p);
    	Q.push(q);
    
            //2 trees differ in size
    	if(P.size() != Q.size()) return false;
    
    	while(!P.empty() && !Q.empty()){
    		TreeNode* pNode = P.front();
    		TreeNode* qNode = Q.front();
    		P.pop();
    		Q.pop();
    
                    //1 in 2 leaves is empty
    		if( pNode == NULL && qNode != NULL ||
    	            qNode == NULL && pNode != NULL) return false;
    
    		if(qNode && pNode){
                            //test values
    			if(qNode->val != pNode->val) return false;
    
    			P.push(pNode->left);
    			P.push(pNode->right);
    			Q.push(qNode->left);
    			Q.push(qNode->right);
    		}
    	}
    	return true;
    	
    }

Log in to reply
 

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