面试题28. 对称的二叉树

对称的二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

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

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

---

示例：

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

---

提示：
0 <= 节点个数 <= 1000

转载来源：力扣（LeetCode）

---

题目分析

这题让我了解了Java的Deque是不可以存放Null的，在这里卡了很久！
如果一棵树是对称的二叉树，那么他中序遍历（先左后右）和中序遍历（先有后左）的输出是一样的，基于这一性质，我分别用DFS和BFS都实现了一遍，代码分别如下（BFS用了两个栈实现，看题解的时候发现只需要用一个，同时push两个和同时poll两个就可以了，我的脑子哎）：

fun isSymmetric(root: TreeNode?): Boolean {
        return isSymmetric(root, root)
    }

    fun isSymmetric(left: TreeNode?, right: TreeNode?): Boolean {
        if (left == null && right == null) return true
        if (left == null || right == null) return false
        return left.`val` == right.`val`
                && isSymmetric(left.right, right.left)
                && isSymmetric(left.left, right.right)
    }

fun isSymmetric(root: TreeNode?): Boolean {
        if (root == null)
            return true
        val leftQueue = ArrayDeque<TreeNode>()
        val rightQueue = ArrayDeque<TreeNode>()
        if (root.left != null)
            leftQueue.push(root.left)
        if (root.right != null)
            rightQueue.push(root.right)
        while (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
            val tmpLeft = leftQueue.poll()
            val tmpRight = rightQueue.poll()
            if (tmpLeft.`val` != tmpRight.`val`)
                return false
            if (tmpLeft.left != null && tmpRight.right != null) {
                leftQueue.push(tmpLeft.left)
                rightQueue.push(tmpRight.right)
            } else if (tmpLeft.left == null && tmpRight.right == null) {
            } else {
                print(" false")
                return false
            }
            if (tmpLeft.right != null && tmpRight.left != null) {
                leftQueue.push(tmpLeft.right)
                rightQueue.push(tmpRight.left)
            } else if (tmpLeft.right == null && tmpRight.left == null) {
            } else {
                print(" false")
                return false
            }
        }
        return (leftQueue.isEmpty() && rightQueue.isEmpty())
    }

代码文件

---