剑指Offer对答如流系列 - 对称的二叉树

栏目: IT技术 · 发布时间: 4年前

内容简介:请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。树的结构如下:

文章目录

  • 面试题28:对称的二叉树

面试题28:对称的二叉树

一、问题描述

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

树的结构如下:

public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

下图中,A是对称的 B C都不是

剑指Offer对答如流系列 - 对称的二叉树

二、问题分析

根节点直接比较即可,我们重点分析左右子树。

剑指Offer对答如流系列 - 对称的二叉树

以上面满足对称的二叉树为例,可以看出,左右子树也刚好是呈镜像的两颗二叉树

剑指Offer对答如流系列 - 对称的二叉树

在比较的时候我们

对左子树可以采用 父节点–> 左节点 --> 右节点 方式遍历 — 6 5 7

对右子树可以采用 父节点–> 右节点 --> 左节点 方式遍历 — 6 5 7

根据顺序 比较即可。

三、问题解答

public boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null) {
            return true; //根结点为null时,认为是对称二叉树
        }
        return isEqual(pRoot.left,pRoot.right);
    }

    private boolean isEqual(TreeNode pRoot1,TreeNode pRoot2){
        if(pRoot1==null && pRoot2==null) {
            return true;
        }
        if(pRoot1==null || pRoot2==null) {
            return false;
        }
        return pRoot1.val==pRoot2.val
                && isEqual(pRoot1.left, pRoot2.right)
                && isEqual(pRoot1.right, pRoot2.left);
    }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

自制编程语言 基于C语言

自制编程语言 基于C语言

郑钢 / 人民邮电出版社 / 2018-9-1 / CNY 89.00

本书是一本专门介绍自制编程语言的图书,书中深入浅出地讲述了如何开发一门编程语言,以及运行这门编程语言的虚拟机。本书主要内容包括:脚本语言的功能、词法分析器、类、对象、原生方法、自上而下算符优先、语法分析、语义分析、虚拟机、内建类、垃圾回收、命令行及调试等技术。 本书适合程序员阅读,也适合对编程语言原理感兴趣的计算机从业人员学习。一起来看看 《自制编程语言 基于C语言》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

随机密码生成器
随机密码生成器

多种字符组合密码