博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Java遍历二叉树深度宽度
阅读量:6163 次
发布时间:2019-06-21

本文共 1652 字,大约阅读时间需要 5 分钟。

节点数据结构

class TreeNode {    TreeNode left = null;    TreeNode right = null;}

 

最大深度,基本思路是:使用递归,分别求出左子树的深度、右子树的深度,两个深度的较大值+1就是最大深度。

// 获取最大深度    public static int getMaxDepth(TreeNode treeNode) {        if (treeNode == null)            return 0;        else {            int left = getMaxDepth(treeNode.left);            int right = getMaxDepth(treeNode.right);            return 1 + Math.max(left, right);        }    }

 

// 获取最小深度    public static int getMinDepth(TreeNode treeNode) {        if (treeNode == null)            return 0;        else {            int left = getMinDepth(treeNode.left);            int right = getMinDepth(treeNode.right);            return 1 + Math.min(left, right);        }    }

 

最大宽度,基本思路:使用队列,按层次遍历二叉树。在上一层遍历完成后,下一层的所有节点已经放到队列中,此时队列中的元素个数就是下一层的宽度。以此类推,依次遍历下一层即可求出二叉树的最大宽度。

// 获取最大宽度    public static int getMaxWidth(TreeNode treeNode) {        if (treeNode == null)            return 0;        Queue
queue = new ArrayDeque
(); int maxWitdth = 1; // 最大宽度 queue.add(treeNode); // 入队 while (true) { int len = queue.size(); // 当前层的节点个数 if (len == 0) break; while (len > 0) {
// 如果当前层,还有节点 TreeNode node = queue.poll(); len--; if (node.left != null) queue.add(node.left); // 下一层节点入队 if (node.right != null) queue.add(node.right);// 下一层节点入队 } maxWitdth = Math.max(maxWitdth, queue.size()); } return maxWitdth; }

 

 

推荐一个在线写白板代码的好地方: 

在线能力评估:

转载于:https://www.cnblogs.com/jager/p/6603510.html

你可能感兴趣的文章
前端js之JavaScript
查看>>
Log4J日志配置详解
查看>>
实验7 BindService模拟通信
查看>>
scanf
查看>>
Socket编程注意接收缓冲区大小
查看>>
SpringMVC初写(五)拦截器
查看>>
检测oracle数据库坏块的方法
查看>>
SQL server 安装教程
查看>>
Linux下ftp和ssh详解
查看>>
跨站脚本功攻击,xss,一个简单的例子让你知道什么是xss攻击
查看>>
js时间和时间戳之间如何转换(汇总)
查看>>
js插件---图片懒加载echo.js结合 Amaze UI ScrollSpy 使用
查看>>
java中string和int的相互转换
查看>>
P1666 前缀单词
查看>>
HTML.2文本
查看>>
Ubuntu unity安装Indicator-Multiload
查看>>
解决Eclipse中新建jsp文件ISO8859-1 编码问题
查看>>
7.对象创建型模式-总结
查看>>
【论文阅读】Classification of breast cancer histology images using transfer learning
查看>>
移动端处理图片懒加载
查看>>