101. 对称二叉树（Swift）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree

题目

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

例如，二叉树 [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-递归

   func isSymmetric(_ root: TreeNode?) -> Bool {
        return isMirror(root1: root, root2: root)
    }
    func isMirror(root1:TreeNode? ,root2:TreeNode?) -> Bool {
        if root1 == nil && root2 == nil {
            return true
        }
        if root1 == nil || root2 == nil {
            return false
        }
        
        return (root1?.val == root2?.val &&
            isMirror(root1: root1?.left, root2: root2?.right) &&
            isMirror(root1: root1?.right, root2: root2?.left))
    }

方法2-迭代，添加到队列，循环判断

struct Queue {
        var queueArr = [TreeNode]()
        var count:Int {
            return queueArr.count
        }
    
        mutating func add(node: TreeNode) -> Void {
            queueArr.append(node)
        }
        mutating func poll() -> TreeNode? {
            if queueArr.count <= 0 {
                return nil
            }
            return queueArr.removeFirst()
        }
    }
   func isSymmetric(_ root: TreeNode?) -> Bool {
        
        var queue = Queue()
        if root != nil {
            queue.add(node: root!)
            queue.add(node: root!)
        }
        //队列里面有node的话，循环判断
        while queue.count > 0 {
            
            let t1 = queue.poll()
            let t2 = queue.poll()
            if t1 == nil && t2 == nil {
                continue
            }
            if t1 == nil || t2 == nil {
                return false
            }
            if t1?.val != t2?.val {
                return false
            }
            if (t1?.left == nil && t2?.right != nil) ||
                (t1?.left != nil && t2?.right == nil){
                return false
            }
            if (t2?.left == nil && t1?.right != nil) ||
                (t2?.left != nil && t1?.right == nil){
                return false
            }
            if t1?.left != nil {
                queue.add(node: (t1?.left)!)
            }
            if t2?.right != nil {
                queue.add(node: (t2?.right)!)
            }
            if t2?.left != nil {
                queue.add(node: (t2?.left)!)
            }
            if t1?.right != nil {
                queue.add(node: (t1?.right)!)
            }
            
        }
        
        return true
    }