100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

  1. //dfs,递归法
  2. func  isSameTree(p *TreeNode, q *TreeNode) bool {
  3.     if p == nil && q == nil {
  4.         return true
  5.     }
  6.     if p == nil || q == nil {
  7.         return false
  8.     }
  9.     if p.Val != q.Val {
  10.         return false
  11.     } 
  13.     return isSameTree(p.Left , q.Left) && isSameTree(p.Right , q.Right)
  14. }
//bfs迭代法，考察细节
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
}