剑指Offer（五十八）-- 对称二叉树

秦怀杂货店

发布于 2022-02-15 14:06:26

1610

发布于 2022-02-15 14:06:26

文章被收录于专栏：技术杂货店

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

示例1

输入

{8,6,6,5,7,7,5}

返回值

true

示例2

输入

{8,6,9,5,7,7,5}

返回值

false

思路以及解答

主要是使用递归，先判断根节点是否为空，不为空则判断左右子树是不是对称。

如果左右子树都为空，则返回true，如果有一个为空，则返回false，如果两个都不为空的时候，除了对比左右两个节点的值，还需要递归，对比左子树的左子树和右子树的右子树是否相等，左子树的右子树和右子树的左子树是否相等。

public class Solution58 {
    public boolean jude(TreeNode left, TreeNode right) {
        // 如果左右两个都为空，则对称
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            // 如果左右两个有一个为空，那么就不对称
            return false;
        }
        // 都不为空的情况，需要判断两个的值，是不是相等
        if (left.val != right.val) {
            return false;
        } else {
            // 递归判断，左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树
            return jude(left.left, right.right) && jude(left.right, right.left);
        }
    }

    public boolean isSymmetrical(TreeNode pRoot) {
        // 判断根节点是否为空，如果不为空则判断左右子树
        return pRoot==null || jude(pRoot.left, pRoot.right);
    }
}

另外一种，非递归的做法，是借助两个队列，按照层次，一个是按照从左到右添加元素，另外一个队列是按照从右到左添加元素，挨个取出来，进行对比，不等则说明不对称，如果相等，则再把其左右子树分别按照不同的顺序添加到队列中。代码如下：

import java.util.LinkedList;

public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if (pRoot == null)
            return true;
        LinkedList<TreeNode> leftNodes = new LinkedList<>();
        LinkedList<TreeNode> rightNodes = new LinkedList<>();
        leftNodes.add(pRoot.left);
        rightNodes.add(pRoot.right);
        while (!leftNodes.isEmpty() && !rightNodes.isEmpty()) {
            TreeNode leftNode = leftNodes.poll();
            TreeNode rightNode = rightNodes.poll();
            if (leftNode == null && rightNode == null)
                continue;
            if (leftNode == null || rightNode == null)
                return false;
            // 取出来对比
            if (leftNode.val != rightNode.val)
                return false;
            // 从左往右添加节点
            leftNodes.add(leftNode.left);
            leftNodes.add(leftNode.right);
            // 从右往左添加节点
            rightNodes.add(rightNode.right);
            rightNodes.add(rightNode.left);
        }
        return leftNodes.isEmpty() && rightNodes.isEmpty();
    }
}

空间复杂度为O(n)，时间复杂度为O(n)。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-23，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树