题目描述

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

示例1

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

示例2

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

题目分析

递归

二叉树对称 等价于 左子树和右子树对称，因此新增一个方法判断两个树 t1 和 t2 是否相互对称。
t1 和 t2 对称 = （两个根节点值相等）且（t1.left 和 t2.right 对称）且（t1.right 和 t2.left 对称）

迭代

使用队列进行层序遍历，判断每一层的数据是否对称

Java

// 递归
// 将问题转化为 左子树 t1 和右子树 t2 对称
// 两个根的值相同，且 t1.left 和 t2.right 对称，t1.right 和 t2.left 对称
public boolean isSymmetric(TreeNode root) {
    return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) {
        return true;
    }
    if (t1 == null || t2 == null) {
        return false;
    }
    return t1.val == t2.val && isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}


// 迭代
// 层序遍历
// 判读每一层是否对称
public boolean isSymmetric2(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 一层入队
        while (size > 0) {
            TreeNode node = queue.poll();
            if (node != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            }
            size--;
        }
        // 检查一层是否对称
        LinkedList<TreeNode> list = new LinkedList<>(queue);
        while (!list.isEmpty()) {
            TreeNode first = list.pollFirst();
            TreeNode last = list.pollLast();
            Integer firstVal = first == null ? Integer.MIN_VALUE : first.val;
            Integer lastVal = last == null ? Integer.MIN_VALUE : last.val;
            if (!firstVal.equals(lastVal)) {
                return false;
            }
        }
    }
    return true;
}

Kotlin

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

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

fun isSymmetric2(root: TreeNode?): Boolean {
    val queue = LinkedList<TreeNode?>()
    queue.offer(root)
    while (!queue.isEmpty()) {
        var size = queue.size
        while (size > 0) {
            val node = queue.poll()
            if (node != null) {
                queue.offer(node.left)
                queue.offer(node.right)
            }
            size--
        }
        val list = LinkedList(queue)
        while (!list.isEmpty()) {
            val first = list.pollFirst()
            val last = list.pollLast()
            val firstVal = first?.`val` ?: Int.MAX_VALUE
            val lastVal = last?.`val` ?: Int.MAX_VALUE
            if (firstVal != lastVal) {
                return false
            }
        }
    }

    return true
}