【力扣】100. 相同的树

给你两棵二叉树的根节点 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] 内
• -104 <= Node.val <= 104

题解：

递归法：

// 时间复杂度：O(n) 这里的 n 是树中节点的数量
// 空间复杂度：O(n) 这里的 n 是树的最大深度
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)
}

迭代法（双队列）：

// 时间复杂度：O(n) 这里的 n 是树中节点的数量
// 空间复杂度：O(n) 这里的 n 是树的最大深度
func isSameTree(p *TreeNode, q *TreeNode) bool {
	queueP := list.New()
	queueQ := list.New()
	queueP.PushBack(p)
	queueQ.PushBack(q)
	for queueP.Len() > 0 || queueQ.Len() > 0 {
		nodeP := queueP.Remove(queueP.Front()).(*TreeNode)
		nodeQ := queueQ.Remove(queueQ.Front()).(*TreeNode)
		if nodeP == nil && nodeQ == nil {
			continue
		}
		if nodeP == nil || nodeQ == nil || nodeP.Val != nodeQ.Val {
			return false
		}
		queueP.PushBack(nodeP.Left)
		queueQ.PushBack(nodeQ.Left)
		queueP.PushBack(nodeP.Right)
		queueQ.PushBack(nodeQ.Right)
	}
	return true
}