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

相关文章

来自专栏决胜机器学习

Redis专题(二) ——Redis数据类型(2)

Redis专题(二)——Redis数据类型(2) (原创内容,转载请注明来源,谢谢) 四、列表类型(List) 列表类型可以存储一个有序的字符串列表,其存储...

3026
来自专栏IT可乐

由HashMap哈希算法引出的求余%和与运算&转换问题

1043
来自专栏大数据杂谈

【Excel】用公式提取Excel单元格中的汉字

1475
来自专栏C/C++基础

迷宫问题(maze problem)——深度优先(DFS)与广度优先搜索(BFS)求解

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

1141
来自专栏开发 & 算法杂谈

序列中查找第二小元素

序列中查找第二小元素有很多方法,本文介绍的是采用分治的思想,自底向上,序列中两两构成一对,比较选出最小值,然后构成上一层序列,然后依次网上构造,最后,根节点就是...

633
来自专栏编程

八大排序算法总结与java实现

概述 因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结。首先罗列一下常见的十大排序算法: ? 请点...

19710
来自专栏张俊红

数据结构—树与二叉树

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

623
来自专栏书山有路勤为径

移除K个数字

LeetCode 402. Remove K Digits 已知一个使用字符串表示的非负整数num,将num中的k个数字移除, 求移除k个数字后,可以获得的...

783
来自专栏King_3的技术专栏

leetcode-22-括号生成

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

682
来自专栏数据结构与算法

P1044 栈

题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一...

2706

扫描关注云+社区