- 浏览: 18751 次
- 性别:
- 来自: 北京
文章分类
最新评论
题目描述
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
解题思路
本题是二叉树的遍历题,但是在深度优先和广度优先上需要进行考虑。如果采用深度优先算法的话,并不能保证另一颗子树的情况,浪费时间,因此采用广度优先算法。本题还是采用两个辅助队列的方式。
自己的代码
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
解题思路
本题是二叉树的遍历题,但是在深度优先和广度优先上需要进行考虑。如果采用深度优先算法的话,并不能保证另一颗子树的情况,浪费时间,因此采用广度优先算法。本题还是采用两个辅助队列的方式。
自己的代码
package leetcode; import java.util.LinkedList; import java.util.Queue; public class MinimumDepthOfBinaryTree { public int minDepth(TreeNode root) { //处理空树 if(root == null) return 0; int depth = 0; Queue<TreeNode> queue1 = new LinkedList<TreeNode>(); Queue<TreeNode> queue2 = new LinkedList<TreeNode>(); queue2.add(root); outer: while(queue2 != null){ depth++; queue1.addAll(queue2); queue2.clear(); while(!queue1.isEmpty()){ TreeNode head = queue1.poll(); if(head.left == null && head.right == null) break outer; if(head.left != null) queue2.add(head.left); if(head.right != null) queue2.add(head.right); } } return depth; } public static void main(String[] args) { TreeNode node1 = new TreeNode(0); TreeNode node2 = new TreeNode(0); TreeNode node3 = new TreeNode(0); TreeNode node4 = new TreeNode(0); node1.left = node2; node1.right = node3; node2.right = node4; MinimumDepthOfBinaryTree mdobt = new MinimumDepthOfBinaryTree(); //System.out.println(mdobt.minDepth(node1)); //System.out.println(mdobt.minDepth(null)); System.out.println(mdobt.minDepth(node3)); } }
发表评论
-
Java中String与StringBuffer的区别
2014-10-29 21:07 294String和StringBuffer的区别,网上资料可以说 ... -
String to Integer (atoi)
2014-10-29 17:13 391题目描述 Implement atoi to convert ... -
Implement strStr()
2014-10-28 15:17 277题目描述 Implement strStr(). Retu ... -
Valid Palindrome
2014-10-23 10:32 413题目描述 Given a string, determine ... -
ZigZag Conversion
2014-10-22 19:51 336题目描述 The string "PAYPALIS ... -
Add Binary
2014-10-22 19:43 296题目描述 Given two binary strings, ... -
Longest Common Prefix
2014-10-22 19:44 323题目描述 Write a function to find t ... -
Count and Say
2014-10-22 19:44 340题目描述 The count-and-say sequence ... -
Valid Sudoku
2014-10-21 10:22 348题目描述 Determine if a Sudoku is v ... -
Valid Parentheses
2014-10-21 09:41 313题目描述 Given a string containing ... -
Palindrome Number
2014-10-21 09:41 341题目描述 Determine whether an integ ... -
Length of Last Word
2014-10-21 09:41 351题目描述 Given a string s consists ... -
Remove Nth Node From End of List
2014-10-20 16:36 251题目描述 Given a linked list, remov ... -
Path Sum
2014-10-20 15:37 287题目描述 Given a binary tree and a ... -
Binary Tree Level Order Traversal II
2014-10-20 11:17 227题目描述 Given a binary tree, retur ... -
Binary Tree Level Order Traversal
2014-10-20 11:03 287题目描述 Given a binary tree, retur ... -
Pascal's Triangle II
2014-10-20 10:07 250题目描述 Given an index k, return t ... -
Pascal's Triangle
2014-10-19 12:24 309题目描述 Given numRows, generate th ... -
Plus One
2014-10-19 11:51 326题目描述 Given a non-negative numbe ... -
Merge Sorted Array
2014-10-18 10:45 390题目描述 Given two sorted integer a ...
相关推荐
Minimum Depth of Binary Tree Maximum Depth of Binary Tree Path Sum Path Sum II Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum Root to Leaf Numbers LCA of Binary Tree 线段...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
Minimum Depth of Binary Tree 本题的要求是给一个二叉树,返回这个二叉树的最小层级 Tips Tmux 基本操作: prefix := Ctrl+B session相关操作 查看/切换session prefix s 离开Session prefix d 重命名当前Session ...
Minimum Depth of Binary Tree(111) 二叉树的遍历包括: 前序遍历 中序遍历 后序遍历 层次遍历 Points: 采用中序遍历实现 若左右子树均不为空,返回深度更小的一个;若其中某一子树为空,返回另一子树的深度 每个...
1.1 树的最小深度Given a binary tree, find its minimum depth.The minimum depth is the n
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 解题思路: 思路一:深度优先遍历,递归遍历左右子树...
Prim's minimum spanning tree Kruskal MST Directed/Undirected graph ops Breadth First Search Depth First Search Dijkstra's algorithm Bellman-Ford algorithm Edmonds-Karp Maximal Flow Push–Relabel ...
12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 ? 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations 312 ...
Imbalance Is Fixed Parameter Tractable.- The Ramsey Number for a Linear Forest versus Two Identical Copies of Complete Graphs.- Computational Geometry.- Optimal Binary Space Partitions in the Plane.-...
The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of ...
12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 ? 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations 312 ...
23.1 Growing a minimum spanning tree 625 23.2 The algorithms of Kruskal and Prim 631 603 Contents ix 24 Single-Source Shortest Paths 643 24.1 The Bellman-Ford algorithm 651 24.2 Single-source shortest...
minimum_depth_binary_tree: twoSum: regularExpressionMathcing: sameTree: find_content_children: LeetCode 算法题 时间复杂度和空间复杂度权衡,时间复杂度的提升是以空间复杂度为代价的 仔细观察,LeetCode 上...
l2.2 Querying a binary search tree 2S6 l2.3 Insertion and deletion 261 l2.4 Randoinly built binary search trees 265 13 Red-Black Thees 273 l3.l Properties of red-black trees 273 l3.2 Rotations 277 l...
5.9 Applications of Depth-First Search 5.10 Depth-First Search on Directed Graphs 5.11 Exercises 6 Weighted Graph Algorithms 6.1 Minimum Spanning Trees 6.2 War Story: Nothing but Nets 6.3 ...
Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its minimum depth = 2. 1:算法遍历二叉树每一层,一旦发现某层的某个结点无子树,就返回该层的深度,这个深度就是该...