刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/same-tree/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你两棵二叉树的根节点 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

思路

BFS、DFS均可

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if (p == nil && q != nil) || (q == nil && p != nil) {
		return false
	}
	pNodeArr := []*TreeNode{p}
	qNodeArr := []*TreeNode{q}
	for i := 0; len(pNodeArr) == len(qNodeArr) && len(pNodeArr) > 0; i++ {
		pTempNodeArr := make([]*TreeNode, 0)
		qTempNodeArr := make([]*TreeNode, 0)
		for j, _ := range pNodeArr {
			if pNodeArr[j].Val != qNodeArr[j].Val {
				return false
			}
			if pNodeArr[j].Left != nil && qNodeArr[j].Left != nil {
				pTempNodeArr = append(pTempNodeArr, pNodeArr[j].Left)
				qTempNodeArr = append(qTempNodeArr, qNodeArr[j].Left)
			} else if pNodeArr[j].Left == nil && qNodeArr[j].Left == nil {

			} else {
				return false
			}
			if pNodeArr[j].Right != nil && qNodeArr[j].Right != nil {
				pTempNodeArr = append(pTempNodeArr, pNodeArr[j].Right)
				qTempNodeArr = append(qTempNodeArr, qNodeArr[j].Right)
			} else if pNodeArr[j].Right == nil && qNodeArr[j].Right == nil {

			} else {
				return false
			}
		}
		pNodeArr = pTempNodeArr
		qNodeArr = qTempNodeArr
	}
	return true
}

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)
}