初级算法-树-对称二叉树

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

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

摘一个示例做个说明.
示例 1：
二叉树 [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

条件分析:

1. 二叉树 -> 递归
2. 堆成 -> 同级left ,right 相同,不同级的中心对称

解决思路1:

1. 根据分析1,采用递归操作实现
2. 根据分析2,先判断树是否存在.然后递归操作

先判断树是否存在.然后递归操作.不存在,则返回true.存在,然后判断左右是否相等.采用函数递归方式.先判断是否存在左右节点.都不存在则返回true,一个存在则返回false.都存在则判断左右节点值是否相同,不同则返回false.然后再递归左树的左节点和右树的右节点(对称位置)及左树的右节点和右树的左节点.

func isSymmetric(_ root: TreeNode?) -> Bool {
 
    guard let tree = root else {
        return true
    }

    return isSymmetric(tree.left, tree.right)
}

func isSymmetric(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
    // 左右节点是否存在,都不存在则返回true
    if left == nil && right == nil {
        return true
    }
    // 如果其中一个节点不存则返回false,或者节点值不相等
    guard let leftTree = left , let rightTree = right, leftTree.val != rightTree.val else {
        return false
    }
    // 返回左右节点的字节点是否对称相应节点
    return isSymmetric(leftTree.left, rightTree.right) && isSymmetric(leftTree.right, rightTree.left)
}

测试用例:

let root = TreeNode()
root.val = 1
let firLeft = TreeNode()
firLeft.val = 2
let firRight = TreeNode()
firRight.val = 2
let secFirLeftLeft = TreeNode()
secFirLeftLeft.val = 3
let secFirLeftRight = TreeNode()
secFirLeftRight.val = 4
let secFirRightLeft = TreeNode()
secFirRightLeft.val = 4
let secFirRightRight = TreeNode()
secFirRightRight.val = 3
root.left = firLeft
root.right = firRight
firLeft.left = secFirLeftLeft
firLeft.right = secFirLeftRight
firRight.left = secFirRightLeft
firRight.right = secFirRightRight

考察要点:

• 树
• 深度搜索优先
• 广度搜索优先
• 二叉树