剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。

分析:本题是一道典型的“分治法”。要求一棵二叉树的高度,我们可以将问题分解,先分别求左右子树的高度,然后取较大值加一即为整棵二叉树的高度。接下来按照这种思路继续求左右子树的高度,直到子树为叶子结点时,此时树(即叶子结点)的高度为1。

/**
 * 题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。
 * @author 大闲人柴毛毛
 * @date 2016年3月31日
 */
public class TreeHeight {
	/**
	 * 分析:本题是一道典型的“分治法”。要求一棵二叉树的高度,我们可以将问题分解,先分别求左右子树的高度,然后取较大值加一即为整棵二叉树的高度。
	 * 接下来按照这种思路继续求左右子树的高度,直到子树为叶子结点时,此时树(即叶子结点)的高度为1。
	 */
	
	/**
	 * 计算二叉树的深度
	 * @param root 二叉树的根结点
	 * @return 返回深度(返回-1表示程序出错)
	 */
	public static <T> int getTreeHeight(Node<T> root){
		//健壮性判断:若树为空
		if(root==null){
			System.out.println("树为空!");
			return -1;
		}
		
		//若当前结点为叶子结点
		if(root.left==null && root.right==null)
			//返回树的高度
			return 1;
		
		// 如果当前结点只有左子树
		else if (root.right == null) 
			// 计算右子树的高度+1
			return getTreeHeight(root.right) + 1;
		
		// 若当前结点只有右子树
		else if (root.left == null) 
			return getTreeHeight(root.left) + 1;
		
		// 若当前结点有左右子树
		else {
			// 从左右子树中挑选出较高的那一棵,再把高度+1
			int left_height = getTreeHeight(root.left);
			int right_height = getTreeHeight(root.right);
			return (left_height > right_height ? left_height : right_height) + 1;
		}
		
	}
	
}

/**
 * 二叉树的结点 
 */
class Node<T>{
	Node<T> left;
	Node<T> right;
	T data;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏jeremy的技术点滴

解决zookeeper导致tomcat停止时报异常的问题

6895
来自专栏吴小龙同學

Gradle for Android(三)多渠道打包、配置签名信息

系列博客 Gradle for Android(一)基本配置、依赖管理 Gradle for Android(二)全局设置、自定义BuildConfig、混淆...

2776
来自专栏依乐祝

[译]ASP.NET Core Web API 中使用Oracle数据库和Dapper看这篇就够了

文章地址: https://www.cnblogs.com/yilezhu/p/9276565.html

901
来自专栏尚国

S2-057远程代码执行漏洞复现过程

https://github.com/vulhub/vulhub/tree/master/struts2/s2-048

2033
来自专栏SpringBoot 核心技术

第三十一章:SpringBoot配置文件application.properties参数详解

1524
来自专栏晓晨的专栏

Entity Framework Core 2.0 使用入门

1493
来自专栏hotqin888的专栏

EngineerCMS核心代码

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

992
来自专栏10km的专栏

java nio: walkFileTree实现文件夹复制移动删除

从java 1.7开始,java提供了java.noi.file.Files类用于更方便的实现文件/文件夹操作。 在Files中提供了丰富的静态方法用于文件...

2898
来自专栏盟主来了

淘宝的npaliedit在mb下会崩溃的问题解决了

1495
来自专栏james大数据架构

常见的几种Flume日志收集场景实战

  这里主要介绍几种常见的日志的source来源,包括监控文件型,监控文件内容增量,TCP和HTTP。 Spool类型   用于监控指定目录内数据变更,若有新文...

2605

扫码关注云+社区