`
淡淡的一抹
  • 浏览: 18751 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Minimum Depth of Binary Tree

 
阅读更多
题目描述
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));
	}
}
分享到:
评论

相关推荐

    cpp-算法精粹

    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 线段...

    LeetCode:LeetCode解决方案

    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-...

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...

    minimum-depth-of-binary-tree.rar_leetcode

    leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度

    leetcode下载-ARTS-:ARTS打卡

    Minimum Depth of Binary Tree 本题的要求是给一个二叉树,返回这个二叉树的最小层级 Tips Tmux 基本操作: prefix := Ctrl+B session相关操作 查看/切换session prefix s 离开Session prefix d 重命名当前Session ...

    LeetCode判断字符串是否循环-leetcode:用lin编码

    Minimum Depth of Binary Tree(111) 二叉树的遍历包括: 前序遍历 中序遍历 后序遍历 层次遍历 Points: 采用中序遍历实现 若左右子树均不为空,返回深度更小的一个;若其中某一子树为空,返回另一子树的深度 每个...

    maycope#Leetcode-Classic#1.1树的最小深度1

    1.1 树的最小深度Given a binary tree, find its minimum depth.The minimum depth is the n

    LeetCode最全代码

    * [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]...

    最大公共字符串leetcode-leetcode:坚持每周刷一道LeetCode题

    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. 解题思路: 思路一:深度优先遍历,递归遍历左右子树...

    数据结构常用算法c++实现

    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 ...

    Computing and Combinatorics

    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.-...

    算法导论--Introduction.to.Algorithms

    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 ...

    算法导论-introduction to algrithms 3rd edition

    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...

    leetcode分发糖果-LeetCodeAlgorithm:学习算法,LeetCode刷题,建议经典书籍《算法导论》《算法4》,使用C++和

    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...

    The Algorithm Design Manual (2rd Edition)

    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 ...

    Python实现二叉树的最小深度的两种方法

    Given binary tree [3,9,20,null,null,15,7],  3  / \  9 20  / \  15 7 return its minimum depth = 2. 1:算法遍历二叉树每一层,一旦发现某层的某个结点无子树,就返回该层的深度,这个深度就是该...

Global site tag (gtag.js) - Google Analytics