题目:给定一个二叉树,找出其最小深度。注意,最小深度的定义是:从根节点到最近叶子节点的最短路径上的节点数量,当一棵树只有一个根节点时,其最小深度是1。说明: 叶子节点是指没有子节点的节点。本篇经验将分享如何通过递归调用来获取一棵二叉树的最小深度。
工具/原料
1
Eclipse
2
JDK1.8
方法/步骤
1
定义节点类,并编写递归调用的算法计算二叉树最小深度图1示,通过静态内部类的形式定义二叉树节点类图2示,递归调用获取二叉树的最小深度,注意对于左右子树中某一个为空的情况的处理逻辑
3
运行测试代码,并在平台提交算法图1示,运行主方法,观察控制台的输出,符合预期图2示,在平台提交算法,测试通过
4
算法总结该算法依然是递归调用在二叉树中的典型应用,注意对于特殊情况的处理逻辑(即左右子树中有一棵为空)。
注意事项
1
当一棵树只有一个根节点时,其最小深度是1
2
在树结构中,叶子节点是指没有任何子节点的节点