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

相关文章

来自专栏大闲人柴毛毛

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

题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。 分析:所谓平衡二...

2895
来自专栏用户画像

4.5.2 平衡二叉树

为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树...

782
来自专栏开发与安全

数据结构:二叉树的定义和性质以及特殊二叉树

一、二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树...

1747
来自专栏Android相关

二叉查找树(Binary Search Tree)

在二叉搜索树b中查找x的过程为: 若b是空树,则搜索失败,否则: 若x等于b的根节点的数据域之值,则查找成功;否则: 若x小于b的根节点的数据域之值,则搜...

1333
来自专栏Android机动车

数据结构——树、森林和二叉树的转换

森林是由若干棵树组成的,所以可以完全理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。步骤不如:

662
来自专栏郭耀华‘s Blog

数据结构二叉树知识点总结

872
来自专栏撸码那些事

【图解数据结构】 树

973
来自专栏calmound

poj 3083 Children of the Candy Corn(搜索)

http://poj.org/problem?id=3083 题意:迷宫沿着左墙走,和沿着右强的距离以及最短路径的距离分别是多少,当向左走的时候1的位置就是面向...

2725
来自专栏猿人谷

判断二叉树是不是平衡

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

1876
来自专栏小文博客

小文’s blog — 平衡二叉树构造方法

873

扫码关注云+社区