对称二叉树

你看那个树叶,像不像你欠我的二百块钱.

沃兹基硕德2020.02.14

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

       1
    /     \
   2       2
 /  \    /   \
3   4   4     3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
  /   \
  2   2
   \   \
   3    3

解题思路

两个树互为镜像的条件：

• 它们的两个根结点具有相同的值
• 每个树的右子树都与另一个树的左子树镜像对称

递归

我们可以通过一个递归函数， 同步移动 两个指针的方法来遍历这棵树，p 指针指向左子树 和 q 指针 指向这棵树的右子树，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

循环

首先我们引入一个队列，这是把 递归程序 改写成 迭代程序 的常用方法。初始化时我们把左右子树入队。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按 相反的顺序 插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

具体实现

递归实现

// isSymmetric 递归实现
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 4:37 下午 2021/2/14
func isSymmetric(root *TreeNode) bool {
  if root == nil {
    return true
  }
  if nil == root.Left && nil == root.Right {
    return true
  }

  if nil == root.Left || nil == root.Right {
    return false
  }
  return check(root.Left, root.Right)
}

// check 递归检查
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 7:46 下午 2021/2/14
func check(p, q *TreeNode) bool {
  if p == nil && q == nil {
    return true
  }
  if p == nil || q == nil {
    return false
  }
  // 根节点值相等,左节点值等于右节点值
  return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
}

循环实现

// isSymmetric 循环实现
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 7:57 下午 2021/2/14
func isSymmetric(root *TreeNode) bool {
  if root == nil {
    return true
  }
  if nil == root.Left && nil == root.Right {
    return true
  }

  if nil == root.Left || nil == root.Right {
    return false
  }

  queue1, queue2 := []*TreeNode{root.Left}, []*TreeNode{root.Right}

  for len(queue1) > 0 && len(queue2) > 0 {
    if len(queue1) != len(queue2) {
      // 数量不等,不可能是镜像
      return false
    }
    node1, node2 := queue1[0], queue2[0]
    if node1.Val != node2.Val {
      // 节点的根植不相等
      return false
    }
    if node1.Left != nil && node2.Right == nil || node1.Right != nil && node2.Left == nil {
      return false
    }

    if node1.Left == nil && node2.Right != nil || node1.Right == nil && node2.Left != nil {
      return false
    }
    queue1, queue2 = queue1[1:], queue2[1:]
    if node1.Left != nil {
      queue1 = append(queue1, node1.Left)
    }
    if node1.Right != nil {
      queue1 = append(queue1, node1.Right)
    }
    if node2.Right != nil {
      queue2 = append(queue2, node2.Right)
    }
    if node2.Left != nil {
      queue2 = append(queue2, node2.Left)
    }
  }

  return len(queue1) == 0 && len(queue2) == 0
}