100. 相同的树

image.png

解题思路
相等的前提就是两个树左节点和左节点相等 ，右节点也一样的
迭代使用的是广度搜索 也就是层搜索 使用的数据结构是队列，

  1. package main
  3. import "fmt"
  5. type TreeNode struct {
  6.          Val int
  7.          Left *TreeNode
  8.          Right *TreeNode
  9.  }
  10. func isSameTree(p *TreeNode, q *TreeNode) bool {
  11.      if p==nil&&q==nil{
  12.          return  true
  13.      }
  14.      if p!=nil&&q==nil||p==nil&&q!=nil||p.Val!=q.Val{
  15.          return false
  16.      }
  17.      return isSameTree(p.Left,q.Left)&&isSameTree(p.Right,q.Right)
  18. }
  21. func isSameTree1(p *TreeNode, q *TreeNode) bool {
  22.     if p==nil&&q==nil{
  23.         return  true
  24.     }
  25.     if p!=nil&&q==nil||p==nil&&q!=nil||p.Val!=q.Val{
  26.         return false
  27.     }
  28.     queue :=make([]*TreeNode,0)
  29.     queue = append(queue,p)
  30.     queue = append(queue,q)
  31.     for len(queue)>0{
  32.         pNode :=queue[0]
  33.         qNode :=queue[1]
  35.         if pNode.Val!=qNode.Val{
  36.             return false
  37.         }
  38.         if pNode.Left!=nil&&qNode.Left!=nil {
  39.             queue = append(queue,pNode.Left)
  40.             queue = append(queue,qNode.Left)
  41.         } else if pNode.Left==nil&&qNode.Left!=nil {
  42.             return false
  43.         }else if pNode.Left!=nil&&qNode.Left==nil {
  44.             return false
  45.         }
  46.         if pNode.Right!=nil&&qNode.Right!=nil {
  47.             queue = append(queue,pNode.Right)
  48.             queue = append(queue,qNode.Right)
  49.         }else if pNode.Right==nil&&qNode.Right!=nil {
  50.             return false
  51.         }else if pNode.Right!=nil&&qNode.Right==nil {
  52.             return false
  53.         }
  54.         queue =queue[2:]
  55.     }
  56.     return true
  57. }
  61. func main() {
  62.     t11 := &TreeNode{Val: 1}
  63.     t12 := &TreeNode{Val: 2}
  64.     t11.Left = t12
  65.     t13 := &TreeNode{Val: 1}
  66.     t11.Right = t13
  68.     t21 := &TreeNode{Val: 1}
  69.     t22 := &TreeNode{Val: 1}
  70.     t21.Left = t22
  71.     t23 := &TreeNode{Val: 2}
  72.     t21.Right = t23
  75.     fmt.Println(isSameTree1(t11,t21))
  76. }