111. 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.

思路：

mine思路：

1.采用后序遍历非递归方式，找到叶子节点，记录当时栈内元素的个数到容器中。

2.最后从容器中选择最小的一个输出。


代码如下：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 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) {
         
        int iMinDepth;
        vector<int> depths;
        stack<TreeNode *> s;
         
        TreeNode *p,*q;
        q = NULL;
        p = root;
        if(!root)
            return 0;
        while(p != NULL || s.size() > 0)
        {
            while( p != NULL)
            {
                s.push(p);
                p = p->left;
            }
            if(s.size() > 0)
            {
                p = s.top();
                  
                if( NULL == p->left && NULL == p->right)
                {
                    depths.push_back(s.size());
                }
                  
                if( (NULL == p->right || p->right == q) )
                {
                    q = p;
                    s.pop();
                    p = NULL;
                }
                else
                    p = p->right;
            }
        }
        iMinDepth = depths[0];
        for(int i = 0; i < depths.size(); i++)
        {
            if(depths[i] < iMinDepth)
            {
                iMinDepth = depths[i];
            }
        }
        return iMinDepth;
    }
};

参考其他：http://www.cnblogs.com/bakari/p/4126693.html

有两种求解的思路，一种采用DFS的思想，一种采用BFS的思想，如下代码所示：

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
37
38
39
40
41
42
43
44
45
46
47
struct TreeNode {
    int            val;
    TreeNode*    left;
    TreeNode*    right;
    TreeNode(int x): val(x), left(NULL),right(NULL) {}
};
 
//采用DFS的思想
int maxDepth(TreeNode *root)
{
    if (NULL == root)
        return 0;
    int l = maxDepth(root->left);
    int r = maxDepth(root->right);
 
    return l > r ? l + 1:r+1;
    //以上这两种方式有一种更简便的方法
    //return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
 
//采用BFS的方法，引入队列
int maxDepth(TreeNode *root)
{
    if (NULL == root)
        return 0;
    queue <TreeNode *> que;
    int nCount = 1;
    int nDepth = 0;// 记录队列里面每一层上的元素
 
    que.push(root);
    while(!que.empty()) {
        TreeNode *pTemp = que.front();
        que.pop();
        nCount --;
 
        if (pTemp->left)
            que.push(pTemp->left);
        if (pTemp->right)
            que.push(pTemp->right);
         
        if (nCount == 0) {
            nDepth ++;
            nCount = que.size();
        }
    }
    return nDepth;
}


本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1835237