p111

发表于 | 分类于 |

LeetCode p111 Minimum Depth of Binary Tree 题解

1.题目：

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.

题意：

找出一个二叉树从根节点到子节点的最短距离。

2.解题思路:

注意子节点左右都为空。具体见代码。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
/**
 * 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 ans = Integer.MAX_VALUE;

	public int minDepth(TreeNode root) {
		if (root == null)
			return 0;
		if (root.left == null && root.right == null) {

			return 1;
		}
		
		minDepth(root,0);
		return ans;
	}

	public void minDepth(TreeNode root, int d) {

		if (d >= ans)
			return;
		if (root.left == null && root.right == null) {
			ans = Math.min(d + 1, ans);
		}
		if (root.left != null) {
			minDepth(root.left, d + 1);
		}

		if (root.right != null) {
			minDepth(root.right, d + 1);
		}

		return;
	}
}

4.一些总结：