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.
Example
Given a binary tree as follow:
1
/ \
2 3
/ \
4 5
The minimum depth is 2.
思路
解法一
BFS
一层一层往queue里放node。如果发现某一个node左右都是null,说明找最短路径到这个点就停了。当前的level就是要求的minimum depth。
Code
/** * 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; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ public int minDepth(TreeNode root) { // write your code here if (root == null) { return 0; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int currLevel = 0; while (!queue.isEmpty()) { int size = queue.size(); currLevel++; for (int i = 0 ; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (node.left == null && node.right == null) { return currLevel; } } } return currLevel; } }