博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
21.对称二叉树
阅读量:3977 次
发布时间:2019-05-24

本文共 2025 字,大约阅读时间需要 6 分钟。

文章目录

一、题目描述

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

在这里插入图片描述

进阶:

你可以运用递归和迭代两种方法解决这个问题吗?

二、解题思路

根据题意,要判断二叉树是否对称,就是要比较根节点的左子树和右子树是不是相互翻转的,理解这一点就知道了趋势我们要比较的是来两个数(这两个数是根节点的左右子数),既然要不停的比较左右子树的子节点,所以使用递归是方便的。

对于一颗二叉树,我们如何判断是不是对称的呢?来看看下面的比较过程:

在这里插入图片描述

如图中所示的一颗二叉树,先比较左右子树的根节点:

在这里插入图片描述

下一步,比较左子树的左孩子和右子树的右孩子是不是相等:

在这里插入图片描述

继续比较左子树的右孩子是不是等于右子树的左孩子:

在这里插入图片描述

如果满足上述条件,则说明是一颗对称二叉树。

三、代码编写步骤

递归三部曲

第一,确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。

返回值自然是bool类型。

代码如下:

boolean dfs(TreeNode left, TreeNode right)

第二,终止条件

要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。

节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)

  • 左节点为空,右节点不为空,不对称,return false

  • 左不为空,右为空,不对称 return false

  • 左右都为空,对称,返回true

此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:

  • 左右都不为空,比较节点数值,不相同就return false

    此时左右节点不为空,且数值也不相同的情况我们也处理了。

代码如下:

//递归终止条件一:两个节点都为nullif(left==null && right==null){
return true;}//递归终止条件二:两个条件中有一个为空,说明不对称if(left ==null || right==null){
return false;}//递归终止条件三:值判断不相等时if(left.val != right.val){
return false;}

第三,确定单层递归的逻辑

上面实现了一系列条件,下面需要层层调用递归传入每次比较的节点,递归函数中调用函数本身,每次比较如上面图示:

  • 左节点的左孩子和右节点的右孩子
  • 左节点的右孩子和右节点的左孩子

代码如下:

//递归调用:函数方法本身调用本身        //主要判断:1.左节点的左孩子和右节点的右孩子           //2.左节点的右孩子和右节点的左孩子        return dfs(left.left,right.right) && dfs(left.right, right.left);

四、代码演示

class Solution {
public boolean isSymmetric(TreeNode root) {
//根节点为空直接放回true if(root==null){
return true; } //调用递归函数,比较根节点下的左右子树,左右节点 return dfs(root.left, root.right); } //定义一个递归函数,比较左节点,右节点 boolean dfs(TreeNode left, TreeNode right){
//递归终止条件一:两个节点都为null if(left==null && right==null){
return true; } //递归终止条件二:两个条件中有一个为空,说明不对称 if(left ==null || right==null){
return false; } //递归终止条件三:值判断不相等时 if(left.val != right.val){
return false; } //递归调用:函数方法本身调用本身 //主要判断:1.左节点的左孩子和右节点的右孩子 2.左节点的右孩子和右节点的左孩子 return dfs(left.left,right.right) && dfs(left.right, right.left); }}

转载地址:http://clgki.baihongyu.com/

你可能感兴趣的文章
Linux下ARM汇编教程
查看>>
linux面试题参考答案
查看>>
LINUX驱动之IIC子系统之三I2C的数…
查看>>
LINUX驱动之IIC子系统之三I2C的数…
查看>>
Linux设备驱动之I2C架构分析
查看>>
浅析linux内核中的idr机制
查看>>
i2c子系统之__i2c_first_dynamic_b…
查看>>
linux内核SPI总线驱动分析(一)
查看>>
浅析linux内核中的idr机制
查看>>
source insight使用
查看>>
linux内核SPI总线驱动分析(一)
查看>>
linux设备模型之uart驱动架构分析
查看>>
source insight使用
查看>>
git基本使用
查看>>
七、WordPress配置HTTPS与开启CDN加速
查看>>
CentOS 6.7下MySQL 5.6 yum快速安装及参数详解
查看>>
CentOS6.8二进制安装MySQL5.6
查看>>
centos 6x系统下源码安装mysql操作记录
查看>>
Centos搭建Mysql主从复制
查看>>
centos下部署redis服务环境及其配置说明
查看>>