剑指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);
    }

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

查看所有标签

猜你喜欢:

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

移动的帝国

移动的帝国

曾航、刘羽、陶旭骏 / 浙江大学出版社 / 2014-1-1 / 48.00

日本是全世界移动互联网最发达的国家之一,堪称移动的帝国。在手机游戏、手机支付、移动医疗、移动电子商务、手机电视等方面,日本都充当了全球移动互联网的试验田。 曾经傲视全球的日本运营商将怎样面对转型的挑战?iPhone来势汹汹,如何打破封闭的日本移动互联网体系?日本在智能手机时代的手机游戏、O2O、移动医疗、移动广告等方面,涌现出了哪些值得借鉴的商业模式? 本书作者团队先后数次前往日本调研......一起来看看 《移动的帝国》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具