Minimum Depth of Binary Tree
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.
思路
队列，BFS
解题
c++版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/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root)
return 0;
int Depth=0;
queue<TreeNode*> que;
que.push(root);
int count=que.size();
while(!que.empty()){
TreeNode* tmp=que.front();
que.pop();
count=count-1;
if(!tmp->left and !tmp->right)
return Depth+1;
if(tmp->left)
que.push(tmp->left);
if(tmp->right)
que.push(tmp->right);
if(count==0){
Depth+=1;
count=que.size();
}
}
return Depth;
}
};
python 版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# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return an integer
def minDepth(self, root):
Depth=0
if not root:
return 0
queue=[]
queue.append(root)
count=len(queue)
while len(queue)!=0:
tmp=queue[0]
del queue[0]
count=count-1
if not tmp.left and not tmp.right:
return Depth+1
if tmp.left:
queue.append(tmp.left)
if tmp.right:
queue.append(tmp.right)
if count==0:
Depth+=1
count=len(queue)
return Depth
