2015年6月6日星期六

LeetCode: Minimum Depth of Binary Tree

C++ Solution:

Queue approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct DATA{
    TreeNode* node;
    int level;
    DATA(TreeNode* n, int l):node(n),level(l){}
};

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue< DATA > que;
        if(!root) return 0;
        que.push(DATA(root,1));
        while(!que.empty()){
            DATA current=que.front();//in java, pop() will return element, in c++, not
            que.pop();
            if(!current.node->left && !current.node->right) return current.level;
            if(current.node->left) 
                //not sure whether DATA() is right for initialization an object
                que.push(DATA(current.node->left, current.level+1)); 
            if(current.node->right) 
                que.push(DATA(current.node->right, current.level+1));
        }      
    }
};

Reference:
1. recursion approach: https://helloacm.com/coding-exercise-minimum-depth-of-binary-tree-c-online-judge/
http://blog.theliuy.com/minimum-depth-of-binary-tree/
2. queues approach: http://yucoding.blogspot.com/2013/01/leetcode-question-55-minimum-depth-of.html

JAVA Solution:
Reference: http://gongxuns.blogspot.com/2012/12/leetcode-minimum-depth-of-binary-tree.html


没有评论:

发表评论