Posted on 2014-01-18 16:56
Uriel 閱讀(115)
評論(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 };