导航
导航
文章目录
  1. 题目
  2. 翻译

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

翻译

给出一颗二叉树,找到其最短路径。
最短路径是从根节点到最近的叶子节点的最短路径上的节点数。

类似104. Maximum Depth of Binary Tree,区别在于在求左右子树的最小值时,如果左、右子树中有空树,则直接返回非空子树的高度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;

if (root.left == null && root.right == null)
return 1;
else if (root.left == null)
return minDepth(root.right) + 1;
else if (root.right == null)
return minDepth(root.left) + 1;

return Math.min(minDepth(root.left) + 1, minDepth(root.right) + 1);
}
}

方法二:根据题目,只要找到深度最低的叶子节点即可,因此使用层次遍历,找到第一个叶子节点后,返回其深度。

参考:
http://blog.csdn.net/sbitswc/article/details/26526031