其他
动画:面试必刷之二叉树的深度
点击蓝色 “小鹿动画学编程” 关注我哦!
加个 “星标” ,每天一篇动画喂饱你!
作者 | 小鹿
来源 | 小鹿动画学编程
题目
输入一棵二叉树的根节点,求该树的深度。从根节点到叶子节点依次经过的节点(包含根、叶子节点)形成树的一条路径,最长路径的长度树的深度。
问题分析
通过对以上题目的解读,首先知道二叉树的深度代表的是什么,是从跟几点到最长的叶子节点所遍历的了几个节点数。
我们有两种方式去思考该问题,第一种是,之前分享过按层遍历二叉树,每遍历一层,我们就将计数 + 1,直到遍历完所有层。
第二,之前也做过求最长路径的二叉树的面试题,我们可以对其进行改进,求得最长路径后,得出路径所经历的节点个数,则就是二叉树的深度。
动画实现
解题思路
首先判断输入的树是否为空。
思路一:
按层遍历,对按层遍历的算法进行改进,每遍历一次层进行加一。
思路二:
寻找最长路径,借助遍历最长路径的设计思路记性改进。只需记录两个子树最深的结点为主。
代码实现
JavaScript
Java
Python
测试用例
完全二叉树、非完全二叉树 —— 普通测试 只有左子节点、只有右子节点、只有一个结点二叉树 —— 特殊测试 空树 —— 输入测试
「小鹿动画学编程」用动画的形式和你分享技术!
长按识别二维码关注