内容简介:给定一个二叉树,求这个二叉树的最大深度,一道很简单的二叉树问题,题目一理解,我们很容易就知道,我们要递归去求解,但是这里还是需要思考的是,是不是这道题就一种递归思路?递归实现的代码往往非常简洁,但是仅仅是一个地方的细微差别,反应出来的是两种完全不一样的思路。我们一起来看看。最开始做这道题,我想的非常简单,思路是:把整个二叉树遍历一遍,每个节点都记录一下当前的深度,然后对比求出最大深度即可。于是我写出了下面的代码:
LeetCode 104. Maximum Depth of Binary Tree
给定一个二叉树,求这个二叉树的最大深度,一道很简单的二叉树问题,题目一理解,我们很容易就知道,我们要递归去求解,但是这里还是需要思考的是,是不是这道题就一种递归思路?递归实现的代码往往非常简洁,但是仅仅是一个地方的细微差别,反应出来的是两种完全不一样的思路。我们一起来看看。
不同解法分析
最开始做这道题,我想的非常简单,思路是:把整个二叉树遍历一遍,每个节点都记录一下当前的深度,然后对比求出最大深度即可。于是我写出了下面的代码:
private int max = 1; public int maxDepth(TreeNode root) { if (root == null) { return 0; } helper(root, 1); return max; } private void helper(TreeNode root, int currentDepth) { if (root == null) { return; } max = Math.max(max, currentDepth); helper(root.left, currentDepth + 1); helper(root.right, currentDepth + 1); } 复制代码
你可以看到这里我定义了一个全局变量 max 来记录当前访问过的所有节点中的最大深度,最后遍历完所有节点,max 就是题目要求的解。这么做从时间空间复杂度分析其实都没有啥毛病,但是这么写确实会让代码变得有点冗余,经过思考之后,改进得到下面的代码
public int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; } 复制代码
这里没有定义额外的全局变量或者辅助函数,递归和之前不同的点仅仅是 “更新值” 先后的问题,而且有一点特别重要的是这里的递归是带返回值的,之前的递归是不带返回值的。那这说明什么呢?是说明带返回值的递归一定就比不带返回值的递归更优吗?其实不是,我们要根据具体情况具体分析,针对这道题,这两种解法确实第二种来的更为简洁,但是明白思路更加的重要,第一种的思路是有点类似 遍历 ,但是这里用的是递归去遍历,并不是我们通常使用的 for 循环, 每到一个树节点就去做一下相应的记录,然后去到下一个树节点做类似的记录,最后把所有的记录汇总就是我们要的答案 ,第二种思路其实就是 分治 ,它的核心是 先分再合 ,每个节点只负责分跟合,这里的分就是当前树节点如果有子节点就分下去,合是指将子节点的结果以及当前的值进行统一、合并。你可能会觉得分治就一定比之前的递归遍历更优,先别急着下这个结论,看看树的中序遍历吧, LeetCode 94. Binary Tree Inorder Traversal ,思考一下,试着用两种不同的思路去解,相信你会得出和这道题完全相反的结论。
思路总结
之前做了挺多的深度优先相关的算法题,像是排列问题,组合问题,N 皇后问题,这些题目都是回溯的思想,条件满足就更新,你很少会去关注当前层和上面一层的联系,这里的递归也不需要任何的返回值,原因很简单,每一层不需要向上一层反应情况,操作都是基于全局变量或者堆内存的。但是反观 分治 则情况大不相同,可以举一个我们工作生活中的例子来加以说明:
老板 / | \ 经理...经理 / | \ / | \ 员工...员工 员工...员工 复制代码
这里一个公司只有一个老板,老板管理着很多的部门,每接到项目,老板都会将这些项目交给不同的部门去做,我们这里假设部门之间相互没有联系(分治算法中不存在重复子问题),每个部门由一个经理来负责,经理会将项目拆分成小任务并分配给不同的员工去处理,到这里,分配就结束了。员工做完了分配的任务后,向上汇报情况,经理将所有员工汇报的情况整合,继续向上汇报,最后老板根据所有部门经理汇报的情况来产生出公司的策略,也就是最后的解。这个例子很好的解释了分治算法的思想,不一样的是,这个例子中的员工、经理、老板做的是不一样的事情,但是分治算法会更加的简单,每一层做的事情都是一样的,只是根据子问题得到的数据不一样,因而结果就会不一样。你可以看到分治其实就是 先分再合,自底向上传递结果的过程 。因为要传递结果,所以递归函数往往就需要有返回值,但是这并不绝对,像 快速排序 这样利用分治思想的算法的递归函数就没有返回值,这是因为它的结果都会记录在同一个数组中。
延伸
看完上面的内容你可能会有一个疑问,是不是深度优先搜索必须依靠递归来实现?其实并不是,函数递归本质上是函数调用函数自己,在系统的底层,我们借助的是函数栈来保存之前的函数,也就是上一层的内容,如果不使用递归,那么就是说我们不能依靠系统为我们提供的函数栈,因此我们需要手动建立一个栈来保存上一层需要的内容,对于这道简单的二叉树问题,代码如下:
public int maxDepth(TreeNode root) { if (root == null) { return 0; } Stack<TreeNode> stackTree = new Stack<>(); Stack<Integer> stackDepth = new Stack<>(); stackTree.push(root); stackDepth.push(1); int max = 1; while (!stackTree.isEmpty()) { TreeNode curNode = stackTree.pop(); int curDepth = stackDepth.pop(); if (curNode.left != null) { stackTree.push(curNode.left); stackDepth.push(curDepth + 1); } if (curNode.right != null) { stackTree.push(curNode.right); stackDepth.push(curDepth + 1); } if (curNode.left == null && curNode.right == null) { max = Math.max(max, curDepth); } } return max; } 复制代码
这里我用了两个栈的原因是有两个变量需要保存,一个是节点,另一个是节点对应的深度,当然你也可以把他们合二为一作为一个新的 Object。自己手动实现一遍,相信会加深你对递归的理解。
其实在普通的深度优先搜索算法的基础之上,我们也可以看到动态规划的影子。一般的深度优先搜索是对之前的子问题的结果不进行保存的,就拿这道题为例子,当你得到最后的解的时候,这时你只知道整颗树的最大深度,但是你并不知道左子树,以及右子树的最大深度,想要知道的话,就得重新再针对左子树或者右子树深度优先搜索走一遍,但是,其实你之前计算整颗树的最大深度的时候,已经将左子树和右子树的最大深度计算过了,因为(maxDepth = Max(leftMaxDepth, rightMaxDepth))+ 1,如果我们用一个数据结构,比如数组或者散列,去记录这些子问题的解,用到的时候直接去这些数据结构中对应着找,那么这样的思想就是动态规划,只是这时它是以递归的形式呈现在这里。当然在这道题当中,记不记录并没有区别,因为没有重复的子问题,换句话说就是除根节点外,一个节点有且仅有一个父节点。可以看之前我分析过的一个算法题 LeetCode 312 Burst Balloons 思路分析总结 ,这里面提到了一个很好的分析搜索类,以及动态规划类问题的思路步骤就是:
- 暴力的深度优先搜索
- 画出/思考出问题和子问题的关系,看有没有重复子问题
- 如果有重复子问题,考虑增加记忆化的数据结构
- 据此,思考动态规划的状态和递推方程
- 实现动态规划
这些步骤并不是对于每到题都要走完的,对于像排列、组合这类问题到第二步就结束了,但是对于很多动态规划问题我们需要一直走完五个步骤,虽然繁琐了些,但是确实可以加强我们方向和思路。以我往常的经验,动态规划问题怕就怕在没有思路,没有思路就会寸步难行。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- LFU五种实现方式,从简单到复杂
- LFU 五种实现方式,从简单到复杂
- 从简单日志到全链路日志 我们应该怎么打日志
- 从简单的即时聊天来看架构演变by golang
- JS中的数组过滤,从简单筛选到多条件筛选
- go-fastdfs是一个基于http的分布式文件系统,它基于大道至简的设计理念,一切从简设计,使得它的运...
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
硅谷产品:36讲直通世界级产品经理
曲晓音 / 电子工业出版社 / 2018-10 / 59
《硅谷产品:36讲直通世界级产品经理》是Facebook资深产品经理曲晓音撰写的产品实战教程,立足于作者在Facebook、Instagram、Microsoft、Atlassian等硅谷科技公司的工作经验,分享硅谷先进的产品思维和方法论,用实际案例带领读者了解硅谷产品经理的所想所做。 《硅谷产品:36讲直通世界级产品经理》适合产品经理从业者、想要提升产品理解能力的技术运营人员、刚刚入行或者......一起来看看 《硅谷产品:36讲直通世界级产品经理》 这本书的介绍吧!