首页 > 代码库 > LinCode 刷题 之二叉树最小深度
LinCode 刷题 之二叉树最小深度
http://www.lintcode.com/zh-cn/problem/minimum-depth-of-binary-tree/ 题目描述信息
二叉树的结构定义如下:
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */
给出一棵如下的二叉树:
1
/ \
2 3
/ \
4 5
这个二叉树的最小深度为 2
思路 层级访问儿二叉树某个节点的左子树和右子数都没有 就是最小深度,广度优先遍历二叉树即可(队列)
1 public class Solution { 2 /** 3 * @param root: The root of binary tree. 4 * @return: An integer. 5 */ 6 public int minDepth(TreeNode root) { 7 Queue<TreeNode> queue=new LinkedList<TreeNode>(); 8 9 int num; 10 if(root==null){ 11 num=0; 12 }else{ 13 num=1; 14 queue.add(root); 15 } 16 while(!queue.isEmpty()){ 17 int size = queue.size(); 18 //遍历本层级的所有元素 19 for(int i=0;i<size;i++){ 20 TreeNode node = queue.poll(); 21 if(node.left==null&&node.right==null){ 22 queue=new LinkedList<>();//找到最深节点返回 23 return num; 24 }else{ 25 if(node.left!=null){ 26 queue.offer(node.left); 27 } 28 29 if(node.right!=null){ 30 queue.offer(node.right); 31 } 32 } 33 } 34 //层级+1 35 num++; 36 37 } 38 39 return num; 40 } 41 }
LinCode 刷题 之二叉树最小深度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。