二叉树的最小深度问题
admin
2024-03-25 07:42:43
0

二叉树的最小深度问题

作者:Grey

原文地址:

博客园:二叉树的最小深度问题

CSDN:二叉树的最小深度问题

题目描述

给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。

题目链接见:LeetCode 111. Minimum Depth of Binary Tree

本题可以用两种方法来解,第一种方法,使用二叉树的递归套路,第二种方法是 Morris 遍历。

二叉树的递归套路解法

相关介绍见:使用二叉树的递归套路来解决的问题

定义递归函数

int minDepth(TreeNode head)

递归含义表示:以 head 为头的二叉树的最小深度为多少。

接下来是 base case,

if (null == head) {return 0;
}

显而易见,空树的深度是0;

接下来是普遍情况:

如果 head 的左树为空,则最小深度就是右树的最小深度加1;

如果 head 的右树为空,则最小深度就是左树的最小深度加1;

如果 head 的左右树都不为空,则最小深度就是左右树深度更大的那个加1。

完整代码如下

  public static int minDepth(TreeNode head) {if (head == null) {return 0;}if (head.left == null) {return minDepth(head.right) + 1;}if (head.right == null) {return minDepth(head.left) + 1;}return Math.min(minDepth(head.left), minDepth(head.right)) + 1;}

这个解法的时间复杂度是O(N)

如果递归栈算空间的话,整个算法空间复杂度就是递归栈的复杂度O(N)

Morris 遍历解法

使用 Morris 遍历,可以实现空间复杂度达到O(1),时间复杂度保持O(N),Morris算法的介绍见:Morris 遍历实现二叉树的遍历

本题如果要用Morris遍历,需要解决的第一个问题是Morris发现当前层?

即:假设上一个节点是 X,在第 8 层,下一个遍历的节点是 Y,如何判断 Y 在第几层?

结论是:如果Y左树的最右节点是 A(非 X ),Y 必定是第 9 层,如果 Y 左树的最右节点是 X,那 Y 在第 X 层数-Y 的左树的右节点的个数

需要解决的第二个问题是Morris发现叶节点?

结论是:每个结点第二次回到自己的时候,因为要恢复指针,在恢复后,看下是否是叶子节点, 最后要单独遍历一下左树的最右节点。

完整代码见

  public static int minDepth(TreeNode head) {if (head == null) {return 0;}TreeNode cur = head;TreeNode mostRight;int curHeight = 0;int min = Integer.MAX_VALUE;while (cur != null) {mostRight = cur.left;if (mostRight != null) {int duplicate = 1;while (mostRight.right != null && mostRight.right != cur) {duplicate++;mostRight = mostRight.right;}if (mostRight.right == null) {curHeight++;mostRight.right = cur;cur = cur.left;continue;} else {if (mostRight.left == null) {min = Math.min(min, curHeight);}curHeight -= duplicate;mostRight.right = null;}} else {curHeight++;}cur = cur.right;}int rightMostHeight = 1;TreeNode c = head;while (c.right != null) {rightMostHeight++;c = c.right;}if (c.left == null) {min = Math.min(min, rightMostHeight);}return min;}

更多

算法和数据结构笔记

相关内容

热门资讯

安卓系统所有手机通用,揭秘所有... 你有没有发现,现在市面上各种各样的手机,品牌琳琅满目,让人挑花了眼?不过,不管你用的是哪个品牌的手机...
安卓系统变ios系统好用吗,体... 你有没有想过,为什么有些人从安卓手机换到了苹果的iPhone,而且好像换了之后整个人都精神焕发呢?没...
华为安卓系统文件删除,轻松掌握... 你有没有遇到过这种情况?手机里的文件突然不见了,尤其是华为安卓系统里的那些重要文件,真是让人心头一紧...
安卓1.5系统软件,初代智能革... 你有没有想过,手机里的那些看似普通的系统,其实背后藏着无数的故事呢?今天,就让我带你走进安卓1.5系...
安卓 代替系统音效设置,打造个... 你有没有发现,手机里的那些系统音效有时候真的让人有点烦躁呢?比如那个每次接电话时“叮咚”一声,或者是...
安卓系统整体性,构建移动设备的... 你知道吗?在智能手机的世界里,安卓系统就像是个全能的魔术师,它不仅拥有丰富的魔法,还能让各种神奇的魔...
安卓系统能玩鬼泣么?,畅享动作... 你有没有想过,在安卓系统上玩《鬼泣》这款游戏会是怎样的体验呢?没错,就是那个让你热血沸腾、挑战极限的...
安卓系统手机编曲软件,音乐创作... 你有没有想过,用手机也能轻松编曲?没错,就是那个你每天不离手的安卓系统手机!现在,我就要给你揭秘几款...
车载导航显示安卓系统,车载导航... 你有没有发现,现在的车载导航系统越来越智能了?尤其是那些搭载了安卓系统的车载导航,简直就像是个贴心的...
安卓系统启动黑屏,安卓系统启动... 手机屏幕突然黑了,这可怎么办?别急,今天就来和你聊聊安卓系统启动黑屏这个让人头疼的问题。你知道吗,这...
怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...