Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Minimum Depth of Binary Tree-2014.01.18

Posted on 2014-01-18 16:56 Uriel 阅读(89) 评论(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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理