Posted on 2014-01-18 16:56
Uriel 阅读(81)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
求二叉树各个叶子节点的最小深度，BFS，记录深度即可，忘记特判空树，又挂一次。。
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 struct Que {
13 int depth;
14 TreeNode *p;
15 }q[100010];
16
17 int minDepth(TreeNode *root) {
18 int l = 0, r = 1, mx = 0, mi = 1000000;
19 if(root == NULL) return 0;
20 q[0].p = root;
21 q[0].depth = 1;
22 while(l < r) {
23 if(q[l].p->left == NULL && q[l].p->right == NULL) {
24 if(q[l].depth < mi) mi = q[l].depth;
25 }
26 if(q[l].p->left != NULL) {
27 q[r].p = q[l].p->left;
28 q[r].depth = q[l].depth + 1;
29 ++r;
30 }
31 if(q[l].p->right != NULL) {
32 q[r].p = q[l].p->right;
33 q[r].depth = q[l].depth + 1;
34 ++r;
35 }
36 ++l;
37 }
38 return mi;
39 }
40 };