内容简介:请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。树的结构如下:
文章目录
- 面试题28:对称的二叉树
面试题28:对称的二叉树
一、问题描述
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
树的结构如下:
public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }
下图中,A是对称的 B C都不是
二、问题分析
根节点直接比较即可,我们重点分析左右子树。
以上面满足对称的二叉树为例,可以看出,左右子树也刚好是呈镜像的两颗二叉树
在比较的时候我们
对左子树可以采用 父节点–> 左节点 --> 右节点 方式遍历 — 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语言
郑钢 / 人民邮电出版社 / 2018-9-1 / CNY 89.00
本书是一本专门介绍自制编程语言的图书,书中深入浅出地讲述了如何开发一门编程语言,以及运行这门编程语言的虚拟机。本书主要内容包括:脚本语言的功能、词法分析器、类、对象、原生方法、自上而下算符优先、语法分析、语义分析、虚拟机、内建类、垃圾回收、命令行及调试等技术。 本书适合程序员阅读,也适合对编程语言原理感兴趣的计算机从业人员学习。一起来看看 《自制编程语言 基于C语言》 这本书的介绍吧!