求二叉树的最小深度，BFS或者DFS
C++ BFS
1 //111
2 //Runtime: 32 ms (Beats 100%)
3
4 /**
5 * Definition for binary tree
6 * struct TreeNode {
7 * int val;
8 * TreeNode *left;
9 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13 class Solution {
14 public:
15 struct Que {
16 int depth;
17 TreeNode *p;
18 }q[100010];
19
20 int minDepth(TreeNode *root) {
21 int l = 0, r = 1, mx = 0, mi = 1000000;
22 if(root == NULL) return 0;
23 q[0].p = root;
24 q[0].depth = 1;
25 while(l < r) {
26 if(q[l].p->left == NULL && q[l].p->right == NULL) {
27 if(q[l].depth < mi) mi = q[l].depth;
28 }
29 if(q[l].p->left != NULL) {
30 q[r].p = q[l].p->left;
31 q[r].depth = q[l].depth + 1;
32 ++r;
33 }
34 if(q[l].p->right != NULL) {
35 q[r].p = q[l].p->right;
36 q[r].depth = q[l].depth + 1;
37 ++r;
38 }
39 ++l;
40 }
41 return mi;
42 }
43 };
Python DFS
1 #111
2 #Runtime: 808 ms (Beats 60.23%)
3 #Memory: 94.9 MB (Beats 26.2%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 min_dep = 1000000
13 def calDepth(self, root, depth):
14 if root.left == None and root.right == None:
15 self.min_dep = min(self.min_dep, depth)
16 return
17 if root.left != None:
18 self.calDepth(root.left, depth + 1)
19 if root.right != None:
20 self.calDepth(root.right, depth + 1)
21 return
22 def minDepth(self, root):
23 """
24 :type root: TreeNode
25 :rtype: int
26 """
27 if root == None:
28 return 0
29 self.calDepth(root, 1)
30 return self.min_dep
Python BFS
1 #111
2 #Runtime: 626 ms (Beats 98.87%)
3 #Memory: 92.3 MB (Beats 79.39%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def minDepth(self, root):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 if not root:
18 return 0
19 q = deque([root])
20 dep = 1
21 while q:
22 sz = len(q)
23 while sz:
24 sz -= 1
25 node = q.popleft()
26 if not node.left and not node.right:
27 return dep
28 if node.left:
29 q.append(node.left)
30 if node.right:
31 q.append(node.right)
32 dep += 1
33 return ans