剑指 offer代码解析——面试题39判断平衡二叉树(高效方法)

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

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

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

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

上一篇博客中采用了一种较为常规的思路,但由于涉及到重复计算子树的高度,因此性能并不好,接下来提出一种从下而上,依次判断每个子树是否为平衡二叉树的同时计算每棵子树的高度,并将其记录下供上层结点使用。

常规思路请移步至:点击打开链接

上述方法效率很低,因为采用了从上至下的判断方向,因此某些结点的高度被重复计算。

若要避免高度的重复计算,我们需要从下至上计算每棵子树的高度,并保存每棵子树的高度,供上方的结点在计算高度时使用。

若要从下至上遍历结点,那就得使用后序遍历,先遍历左右子树,最后遍历根结点。

/**
 * 题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。
 * 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。
 * @author 大闲人柴毛毛
 * @date 2016年4月2日
 */
public class BalanceTree {
	/**
	 * 上述方法效率很低,因为采用了从上至下的判断方向,因此某些结点的高度被重复计算。
	 * 若要避免高度的重复计算,我们需要从下至上计算每棵子树的高度,并保存每棵子树的高度,供上方的结点在计算高度时使用。
	 * 若要从下至上遍历结点,那就得使用后序遍历,先遍历左右子树,最后遍历根结点。
	 * 代码如下:
	 */
	Height height = new Height();
	public static <T> boolean isBalanceTree_2(Node<T> root,Height height){
		//健壮性判断:若树为空
		if(root==null){
			height.height = 0;
			return true;
		}
		
		Height left_height = new Height();
		Height right_height = new Height();
		//若左右子树均是平衡二叉树
		if(isBalanceTree_2(root.left,left_height) && isBalanceTree_2(root.right,right_height)){
			//判断当前是否为平衡二叉树
			int diff = left_height.height-right_height.height;
			if(diff==-1 || diff==1 || diff==0){
				//计算当前子树的高度
				height.height = (left_height.height<right_height.height ? right_height.height : left_height.height)+1;
				return true;
			}
			return false;
		}
		
		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_2(node1,new Height()));
	}
}

//存放当前树的高度
class Height{
	int height;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

数据结构(六):红黑树

级别的查询、插入和删除节点复杂度。相对于 AVL 树单纯的对每个节点的平衡因子进行判断,红黑树给节点赋予了颜色属性,并通过对树中节点的颜色进行限制,来保持整棵...

792
来自专栏Golang语言社区

43. 等价二叉树 | 厚土Go学习笔记

实现两个二叉树的比较。二叉树的基本类型和函数来源于 “golang.org/x/tour/tree”,为了避免网络问题影响代码运行,我把源码直接加入到了代码中。...

36912
来自专栏琯琯博客

PHP二叉树(三):红黑树

2244
来自专栏null的专栏

挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是...

3344
来自专栏灯塔大数据

每周学点大数据 | No.24二叉搜索树回顾(一)

No.24期 二叉搜索树回顾(一) Mr. 王:接下来我们谈一谈外存查找结构。内存中的查找结构最典型的就是二查搜索树了。这里我们先来简单地认识一下关于二叉树...

3295
来自专栏张俊红

数据结构—树与二叉树

之前谈到的线性表、栈和队列都是一对一的数据结构,但是现实中也存在很多一对多的数据结构,这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分:

723
来自专栏专知

关关的刷题日记98 – Leetcode 106. Construct Binary Tree from Inorder

关关的刷题日记98 – Leetcode 106. Construct Binary Tree from Inorder and Postorder Trave...

3466
来自专栏Java爬坑系列

【Java入门提高篇】Day25 史上最详细的HashMap红黑树解析

  当当当当当当当,好久不见,最近又是换工作,又是换房子,忙的不可开交,断更了一小段时间,最重要的一篇迟迟出不来,每次都犹抱琵琶半遮面,想要把它用通俗易懂的方式...

924
来自专栏曾大稳的博客

树(Tree)以及二叉树的遍历

树(tree) 是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次...

831
来自专栏机器学习从入门到成神

数据结构之判断一棵树是否为完全二叉树

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

661

扫码关注云+社区