相同的树

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

测试用例

case1

输入：p = [1,2,3], q = [1,2,3]
输出：true

case2

输入：p = [1,2], q = [1,null,2]
输出：false

case3

输入：p = [1,2,1], q = [1,1,2]
输出：false

解题思路

深度优先

• 如果两个二叉树都为空，则两个二叉树相同。
• 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
• 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个 递归的过程 ，因此可以使用 深度优先搜索 ，递归地判断两个二叉树是否相同。

广度优先

• 使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作。
• 比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同；
• 如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同；
• 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。

代码实现

深度优先实现

// isSameTree 深度优先对比
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 11:23 下午 2021/2/13
func isSameTree(p *TreeNode, q *TreeNode) bool {
  // 全部是nil，相等
  if nil == p && nil == q {
    return true
  }
  // 只有一个为nil,不相等
  if nil == p || nil == q {
    return false
  }

  // 值不相等
  if p.Val != q.Val {
    return false
  }

  // 递归对比左右子树
  return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

广度优先实现

// isSameTree 广度优先
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 11:28 下午 2021/2/13
func isSameTree(p *TreeNode, q *TreeNode) bool {
  if nil == p && nil == q {
    return true
  }

  if nil == p || nil == q {
    return false
  }

  treeQueue1, treeQueue2 := []*TreeNode{p}, []*TreeNode{q}

  // 两个队列均长度均大于0
  for len(treeQueue1) > 0 && len(treeQueue2) > 0 {
    if len(treeQueue1) != len(treeQueue2) {
      // 队列长度不一样，说明树一定不相等
      return false
    }
    node1, node2 := treeQueue1[0], treeQueue2[0]
    if node1.Val != node2.Val {
      // 节点值不相等
      return false
    }
    treeQueue1, treeQueue2 = treeQueue1[1:], treeQueue2[1:]
    leftNode1, rightNode1 := node1.Left, node1.Right
    leftNode2, rightNode2 := node2.Left, node2.Right
    if (leftNode1 == nil && leftNode2 != nil) || (leftNode1 != nil && leftNode2 == nil) {
      return false
    }
    if (rightNode1 == nil && rightNode2 != nil) || (rightNode1 != nil && rightNode2 == nil) {
      return false
    }

    if nil != leftNode1 {
      treeQueue1 = append(treeQueue1, leftNode1)
    }

    if nil != rightNode1 {
      treeQueue1 = append(treeQueue1, rightNode1)
    }

    if nil != leftNode2 {
      treeQueue2 = append(treeQueue2, leftNode2)
    }

    if nil != rightNode2 {
      treeQueue2 = append(treeQueue2, rightNode2)
    }
  }

  return len(treeQueue1) == 0 && len(treeQueue2) == 0
}