Leetcode-100: same tree

100. Same tree
Title Description ： Here are the root nodes of two binary trees p and q , Write a function to check whether the two trees are the same .
If two trees are the same in structure , And the nodes have the same value , They are the same .

Depth first recursive solution （O(min(m,n)),O(min(m,n))）

class Solution {
    
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
    
        if(p == nullptr && q==nullptr)  return true;
        else if( p== nullptr && q!=nullptr) return false;
        else if( p!= nullptr && q==nullptr) return false;
        else if (p->val != q->val)    return false;
        else {
    
			//  Deliver ————> Judge whether the left and right subtrees are the same 
            return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
        }
    }
};

breadth-first （O(min(m,n)),O(min(m,n))）

class Solution {
    
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
    
        //  First, judge whether the root node meets the conditions 
        if(p == nullptr && q==nullptr)  return true;
        else if(p==nullptr || q==nullptr)   return false;
        //  Initialize two breadth first traversal queues 
        queue<TreeNode*> que1,que2;
        //  Root in line 
        que1.push(p);
        que2.push(q);
        //  Perform hierarchical traversal , Notice here because it's a comparison between two trees 
		//  So it's not like the previous level traversal 
        while(!que1.empty() && !que2.empty()){
    
            //  Get the team leader element every time and judge 
            TreeNode* node1 = que1.front();
            que1.pop();
            TreeNode* node2 = que2.front();
            que2.pop();
            //  Unequal node values indicate different trees 
            if(node1->val!=node2->val)    return false;
            //  Take the four children of the current two team head nodes of the two trees 
            auto cur1 = node1->left,cur2 = node1->right,cur3 = node2->left,cur4 = node2->right;
            //  If only one of the left and right child pointers of the two nodes is empty, it indicates that the tree is different 
            if(cur1==nullptr ^ cur3==nullptr)   return false;
            if(cur2==nullptr ^ cur4==nullptr)   return false;
            //  Nodes that are not empty are queued 
            if(cur1!=nullptr)   que1.push(cur1);
            if(cur2!=nullptr)   que1.push(cur2);
            if(cur3!=nullptr)   que2.push(cur3);
            if(cur4!=nullptr)   que2.push(cur4);
        }
        //  If both teams have finished processing when the hierarchical traversal exits, the tree is the same 
        return que1.empty() && que2.empty(); 
    }
};