题目地址：相同的树

思路解析

文章思路来自左程云老师的算法新手班第六节

两个树相同需要满足结构相同并且每一个节点的值相同

如何保证结构相同，可以使用递归序去遍历，去判断每一个节点的左右分支的情况。

递归结束的条件自然是树被遍历完，下面全空，然后返回结果

同时需要判断节点处是否值相同

那么如何就是结构不相同呢，某一个节点为空，而另一个对应的节点不为空，那么就是结构不同，一定需要返回false，这时使用异或（^）（相同为假，不同为真）就可以判断

if(p == null ^ q == null){
    return false;
}

如果这个条件为假，那么说明这个节点要么同时存在，要么同时不存在，如果同时不存在，就说明树已经遍历完，无需接着判断，返回true即可

if (p == null&&q == null) {
    return true; 
}

如果节点同时不为空，就判断节点的值是否相同，该节点的左右节点是否也结构相同和值相同

所以，递归

return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);

下面是完整代码

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null ^ q == null){
            return false;
        }
        if (p == null&&q == null) {
           return true;
        }
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);
    }