[剑指offer] 二叉树的深度
本文首发于我的个人博客:尾尾部落
题目描述
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
解题思路
法一:递归法。求二叉树的深度,就是求左子树、右子树的中深度最大的加上一个根节点,依此递归即可。
法二:层次遍历。每遍历一层,deep 加 1,直接到最后一层,输出 deep。
参考代码
法一:递归法
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public int TreeDepth(TreeNode root) { if(root == null) return 0; int left = TreeDepth(root.left) + 1; int right = TreeDepth(root.right) + 1; return left > right ? left : right; } }
法二:层次遍历
import java.util.Queue; import java.util.LinkedList; public class Solution { public int TreeDepth(TreeNode root) { if(root == null) return 0; int deep = 0; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); int start = 0, end = 1; while(!queue.isEmpty()){ TreeNode node = queue.poll(); start ++; if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } if(start == end){ end = queue.size(); start = 0; deep ++; } } return deep; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java编程--如何突破程序员思维
过去我曾一直认为程序员是依靠他们的技术在编程,也是因为技术使得程序员的水平有高低之分,但随着我写代码的时间越来越长,也接触到更多的程序员,我渐渐发现程序员们其实是依靠他们所特有的程序员思维在进行编程的,而他们中的佼佼者正是那些有着更高思维成熟度的优秀程序员们。 什么是程序员思维 那么,什么是程序员思维呢?我曾读到过一些文章,试图给它下一个明确的定义,比如,具备抽象和逻辑思维的能力,拥有面向对象编程和设计的能力等等。我对这些所谓定义有些不以为然,因为,我所体会的程序员思维更像是一种感觉,它是由常人的思维+编程思维,长期相互作用下产生的一种思维模式,它能够帮助程序员快速找到以程序方式解决现实问题的最优解。 那么,程序员们又是如何获得这种思维的呢?我想说,从你学习编程并写下你的第一个HelloWorld程序的时候,程序员思维就已经不知不觉地建立起来了,而随着你不断深入地学习与实践,它也变得越来越完整和成熟。下面就是我认为对于提升程序员思维有所帮助的几点建议,虽然不做展开,但相信每个程序员都会认同吧。 长期不间断的编程实践 持续地学习与借鉴(参考) 学会反思,并像专家一样思考 为什么要突破程序...
- 下一篇
LearnJava(三)String、StringBuffer 与 StringBuilder
我们知道,String对象是不可变的,而Java中String类提供了“+”进行字符串拼接操作,从JDK1.5开始,字符串的拼接操作是通过StringBuffer类来完成的。 String a = "str"; String b = "ing"; String c = a + b; 上述代码的实际实现过程是: String c = new StringBuffer(a).append(b).toString(); 也就是说,在这个过程中实际创建了一个StringBuffer对象和一个String对象。因此,当对字符串进行修改的时候,使用 StringBuffer 和 StringBuilder 类,系统开销比较小。 与 String 类不同的是,StringBuffer 和 StringBuilder 类的对象能够被多次的修改,并且不产生新的未使用对象。 区别 String 不可变,而 StringBuffer 和 StringBuilder 是可变的。 StringBuffer 是线程安全的,内部使用 synchronized进行同步,而 StringBuilder 不是...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS8编译安装MySQL8.0.19
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS8安装Docker,最新的服务器搭配容器使用
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Hadoop3单机部署,实现最简伪集群