same-tree

//先序遍历递归
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(!p&&!q)return true;
        if(!p||!q)return false;
        return p->val==q->val&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
};

//后序遍历递归，会比先序遍历的快，因为从下到上
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(!p&&!q)return true;
        if(!p||!q)return false;
        bool f1=isSameTree(p->left,q->left);
        if(f1==false)return false;
        f1=isSameTree(p->right,q->right);
        if(f1==false)return false;
        if(p->val!=q->val)return false;
        return true;
    }
};

//非递归，一个队列实现
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        queue<TreeNode*>qu;
        qu.push(p),qu.push(q);
        while(!qu.empty())
        {
            TreeNode*t1=qu.front();qu.pop();
            TreeNode*t2=qu.front();qu.pop();
            if(!t1&&!t2)continue;//为了判断节点不对应，这里无区别的push进去，然后比较
            if(!t1||!t2)return false;
            if(t1->val!=t2->val)return false;
            qu.push(t1->left);
            qu.push(t2->left);
            qu.push(t1->right);
            qu.push(t2->right);
        }
        return true;
    }
};