剑指 Offer：28. 对称的二叉树

1. 题目

剑指 Offer 28. 对称的二叉树

2. 描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [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： 输入：root = [1,2,2,3,4,4,3] 输出：true 示例 2： 输入：root = [1,2,2,null,3,null,3] 输出：false 限制： 0 <= 节点个数 <= 1000

3. 实现方法

3.1 方法 1

3.1.1 思路

对于对称二叉树，则对于该树中的任意两个对称节点 leftNode 和 rightNode，一定有如下性质：

• leftNode.val = rightNode.val；
• leftNode.left.val = rightNode.right.val；
• leftNode.right.val = rightNode.left.val；

有了上面三条性质，只需要自顶向下递归，判断每对节点是否对称即可；

• 时间复杂度：主要的操作是判断每对节点是否对称，但是需要比较所有节点数，所以时间复杂度为

O(n)

；

3.1.2 实现

代码语言：javascript复制

public boolean isSymmetric(TreeNode root) {
    // root 为 null，则是对称树
    if (root == null) {
        return true;
    }
    // 递归返回左右子树判断结果
    return symmetric(root.left, root.right);
}

public boolean symmetric(TreeNode leftNode, TreeNode rightNode) {
    // 两者均为 null, 则是对称
    if (leftNode == null && rightNode == null) {
        return true;
    }

    // 其中之一为 null,则非镜像
    if (leftNode == null || rightNode == null) {
        return false;
    }

    // 根节点是否对称
    if (leftNode.val != rightNode.val) {
        return false;
    }

    // 判断左右子树
    return symmetric(leftNode.left, rightNode.right) && symmetric(leftNode.right, rightNode.left);
}

二叉树

0 人点赞