100. Same Tree

题目

给定两个二叉树，p, q，编写函数判断两个二叉树是否相同。
相同的二叉树树形相同且每个节点值也相同。

解析

将两个树按相同的遍历方式遍历，期间判断当前节点是否相等即可。

伪代码

代码

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

image.png

这里首先判断当前节点是否是空节点，如果都是空说明相同，就返回 true。然后判断一个为空一个不为空的情况，正常写法应该是 (p == nil && q != nil) || (p != nil && q == nil)。但是前边我们已经判断过 p q 同时为空的情形了，这里如果 p q 有一个为空，那么另一个必然不为空，所以简写为 p == nil || q == nil。