剑指 offer代码解析——面试题39判断平衡二叉树

题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。

分析:所谓平衡二叉树就是要确保每个结点的左子树与右子树的高度差在-1到1之间。

由于之前一题已经给出了二叉树高度的计算方法,因此本题最直观的思路就是分别计算每个结点的左子树高和右子树高,从而判断一棵树的所有结点是否均为平衡二叉树。

/**
 * 题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。
 * 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。
 * @author 大闲人柴毛毛
 * @date 2016年4月2日
 */
public class BalanceTree {
	/**
	 * 分析:所谓平衡二叉树就是要确保每个结点的左子树与右子树的高度差在-1到1之间。
	 * 由于之前一题已经给出了二叉树高度的计算方法,因此本题最直观的思路就是分别计算每个结点的左子树高和右子树高,从而判断一棵树的所有结点是否均为平衡二叉树。
	 * 代码如下:
	 */
	
	public static <T> boolean isBalanceTree_1(Node<T> root){
		//健壮性判断:若树为空
		if(root==null){
			System.out.println("树为空!");
			return true;
		}
		
		// 计算左子树高
		int left_height = TreeHeight.getTreeHeight(root.left);
		// 计算右子树高
		int right_height = TreeHeight.getTreeHeight(root.right);
		// 计算高度差
		int mid = left_height - right_height;
		// 判断高度差是否为-1、0、1
		if (mid == -1 || mid == 0 || mid == 1)
			// 若当前结点是平衡二叉树,则计算左子树和右子树是否为平衡二叉树
			return (isBalanceTree_1(root.left) && isBalanceTree_1(root.right));
		// 若当前结点不是二叉平衡树,则返回false
		else
			return false;
	}
	
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		//构造一棵平衡二叉树
		Node<Integer> node1 = new Node<Integer>();
		Node<Integer> node2 = new Node<Integer>();
		Node<Integer> node3 = new Node<Integer>();
		Node<Integer> node4 = new Node<Integer>();
		Node<Integer> node5 = new Node<Integer>();
		Node<Integer> node6 = new Node<Integer>();
		Node<Integer> node7 = new Node<Integer>();
		Node<Integer> node8 = new Node<Integer>();
		Node<Integer> node9 = new Node<Integer>();
		
		node1.data = 1;
		node2.data = 2;
		node3.data = 3;
		node4.data = 4;
		node5.data = 5;
		node6.data = 6;
		node7.data = 7;
		node8.data = 8;
		node9.data = 9;
		
		node1.left = node2;
		node1.right = node3;
		node2.left = node4;
		node2.right = node5;
		node5.left = node7;
		node3.right = node6;
//		node7.left = node8;
//		node8.left = node9;
		
		System.out.println(isBalanceTree_1(node1));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

在Win10上是用Anaconda搭建TensorFlow开发环境

以下内容原本是作为毕业设计的一部分的,因此绝对认真和详细,由于内容过多所以被删减了,就当福利送给大家了。 2.2 在Windows 10上搭建TensorFl...

2926
来自专栏杨建荣的学习笔记

Oracle备库的PDB无法连接的问题(r11笔记第6天)

今天在测试12c的temp_undo的时候,准备在备库上测试一下,突然发现备库使用TNS连接竟然失败。 抛出的错误如下: $ sqlplus sys/oracl...

3509
来自专栏蜉蝣禅修之道

ubuntu13.10安装broadcom无线网卡驱动

1927
来自专栏大数据学习笔记

Spark2.x学习笔记:1、Spark2.2快速入门(本地模式)

1、Spark2.2快速入门(本地模式) 1.1 Spark本地模式 学习Spark,先易后难,先从最简单的本地模式学起。 本地模式(local),常用于本地开...

63310
来自专栏Objective-C

iOS-安装和使用 CocoaPods

3367
来自专栏Netkiller

以太坊私链入门

中国广东省深圳市龙华新区民治街道溪山美地 518131 +86 13113668890 <netkiller@msn.com>

2.4K9
来自专栏owent

开源项目得一些小维护

其实我那几个特别是工具类得开源项目一致都有维护和更新,但是每次更新得量和要点并不怎么突出所以一致也没写点什么。但是偶尔吗也会碰到一些稍微值得记录的东西,但是又不...

1003
来自专栏杨建荣的学习笔记

DBCA静默建库中的两个小问题 (r9笔记第28天)

创建数据库,主要有手工建库,DBCA建库,OMF建库。手工建库会重新初始化数据字典,过程相对比较耗时,但是完全定制化;OMF建库的场景比较特别, 一般都是糅合在...

3474
来自专栏乐沙弥的世界

[INS-20802] Oracle Net Configuration Assistant failed

        [INS-20802] Oracle Net Configuration Assistant failed。在安装Oracle 11g R2时出...

1784
来自专栏深度学习那些事儿

如何从亚马逊下载aws-SpaceNet卫星遥感图片数据集

亚马逊SpaceNet数据集是作用于机器学习人工智能方面比赛或者研究用的商用数据集。我们在利用深度学习进行卫星图像分割时,比如利用FCN、Deeplab算法进行...

4915

扫码关注云+社区