给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false提示：
- 两棵树上的节点数目都在范围 [0, 100] 内
- -10^4 <= Node.val <= 10^4
解题：
func isSameTree(p *TreeNode, q *TreeNode) bool {
var inorder func(node1, node2 *TreeNode) bool
inorder = func(node1, node2 *TreeNode) bool {
if node1 == nil || node2 == nil {
if node1 == nil && node2 == nil {
return true
} else {
return false
}
}
b1 := inorder(node1.Left, node2.Left)
if node1.Val != node2.Val {
return false
}
b2 := inorder(node1.Right, node2.Right)
return b1 && b2
}
return inorder(p, q)
}官方解答：
1.深度优先搜索
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
if p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}2.广度优先搜索
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
queue1, queue2 := []*TreeNode{p}, []*TreeNode{q}
for len(queue1) > 0 && len(queue2) > 0 {
node1, node2 := queue1[0], queue2[0]
queue1, queue2 = queue1[1:], queue2[1:]
if node1.Val != node2.Val {
return false
}
left1, right1 := node1.Left, node1.Right
left2, right2 := node2.Left, node2.Right
if (left1 == nil && left2 != nil) || (left1 != nil && left2 == nil) {
return false
}
if (right1 == nil && right2 != nil) || (right1 != nil && right2 == nil) {
return false
}
if left1 != nil {
queue1 = append(queue1, left1)
}
if right1 != nil {
queue1 = append(queue1, right1)
}
if left2 != nil {
queue2 = append(queue2, left2)
}
if right2 != nil {
queue2 = append(queue2, right2)
}
}
return len(queue1) == 0 && len(queue2) == 0
}