剑指 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 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a h...

1599
来自专栏desperate633

LintCode 二叉树的最小深度题目代码

430
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1624
来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

40811
来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

1826
来自专栏编程理解

数据结构(四):平衡二叉树(AVL树)

。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

373
来自专栏mathor

LeetCode110.平衡二叉树

 平衡二叉树的定义是一个二叉树每个结点的左右两个子树的高度差绝对值不超过1(可以是1),用一个结构体来保存某个结点的信息(包括是否是平衡树,高度多少),算法...

573
来自专栏desperate633

LintCode 最近公共祖先题目代码

582
来自专栏尾尾部落

[剑指offer] 二叉树的镜像

通过对以上两棵树的观察,我们可以总结出这两棵树的根节点相同,但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程:先前序遍历这棵树的每个节点...

482
来自专栏java学习

面试题65(树,图)

面试例题1:前序遍历二叉树值为abcdefg,下面哪个不可能是中序遍历?A.abcdefg B.gfedcba C.bcdefga D.bceadfg 正确解析...

2694

扫描关注云+社区