对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1： 输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2： 输入：root = [1,2,2,null,3,null,3] 输出：false

提示： 树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100

解题思路

  • 递归法(dfs)
    • 终止条件是左右节点都是nil
  • 迭代法(bfs)
func isSymmetric(root *TreeNode) bool {
  	if root == nil {
  		return false
  	}
  	var queue = make([]*TreeNode, 0)
  	queue = append(queue, root.Left, root.Right)
  	for len(queue) > 0 {
  		left, right := queue[0], queue[1]
  		queue = queue[2:]
  		if left == nil && right == nil {
  			continue
  		}
  		if left == nil || right == nil || left.Val != right.Val {
  			return false
  		}
  
  		// 注意：添加子树时顺序，由于对称性问题
  		queue = append(queue, left.Left, right.Right)
  		queue = append(queue, left.Right, right.Left)
  	}
  	return true
  }
  
  func isSymmetric1(root *TreeNode) bool {
  	if root == nil {
  		return true
  	}
  	
  	return isMirror(root.Left, root.Right)
  }
  func isMirror(left, right *TreeNode) bool {
  	if left == nil && right == nil {
  		return true
  	}
  	if left == nil || right == nil || left.Val != right.Val {
  		return false
  	}
  	return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}