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

相关文章

来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

2593
来自专栏java学习

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

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

60411
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

2258
来自专栏曾大稳的博客

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

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

1481
来自专栏小文博客

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

993
来自专栏软件开发 -- 分享 互助 成长

二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,...

20310
来自专栏郭耀华‘s Blog

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

972
来自专栏撸码那些事

【图解数据结构】 树

1173
来自专栏大闲人柴毛毛

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

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

2945
来自专栏菩提树下的杨过

数据结构C#版笔记--树与二叉树

                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以...

2498

扫码关注云+社区