Leetcode-100：相同的树

100. 相同的树
题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

深度优先递归解决（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 {
    
			// 递————>判断左右子树是否相同
            return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
        }
    }
};

广度优先（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;
        // 初始化两个广度优先遍历队列
        queue<TreeNode*> que1,que2;
        // 根节点入队
        que1.push(p);
        que2.push(q);
        // 进行层次遍历，注意这里因为是两个树之间的比较
		// 所以就不像以前的层次遍历
        while(!que1.empty() && !que2.empty()){
    
            // 每次获取队首元素并判断
            TreeNode* node1 = que1.front();
            que1.pop();
            TreeNode* node2 = que2.front();
            que2.pop();
            // 节点值不相等说明树不相同
            if(node1->val!=node2->val)    return false;
            // 取两个树当前两个队首节点的四个孩子
            auto cur1 = node1->left,cur2 = node1->right,cur3 = node2->left,cur4 = node2->right;
            // 判断两个节点的左右孩子指针只有其中一个为空则说明树不相同
            if(cur1==nullptr ^ cur3==nullptr)   return false;
            if(cur2==nullptr ^ cur4==nullptr)   return false;
            // 不为空的节点入队
            if(cur1!=nullptr)   que1.push(cur1);
            if(cur2!=nullptr)   que1.push(cur2);
            if(cur3!=nullptr)   que2.push(cur3);
            if(cur4!=nullptr)   que2.push(cur4);
        }
        // 如果层次遍历退出时两个队都已经处理完则说明树相同
        return que1.empty() && que2.empty(); 
    }
};