题目链接：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.

这道题的要求是计算二叉树的最小深度。

与Maximum Depth of Binary Tree相反的一道题，同样都可以采用深度优先和广度优先。

  1. 深度优先搜索

递归思路，如果当前节点为NULL，返回0；每次递归一层，记录深度的变量d加1；当遇到左右子树都为NULL的节点的时候，比较并记录最小深度到res即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution 
{
    int res = INT_MAX;
public:
    int minDepth(TreeNode *root)
    {
        minDepth(root, 0);
        return res;
    }
private:
    void minDepth(TreeNode *root, int d)
    {
        if(root == NULL)
            return 0;
        
        ++ d;
        if(root -> left == NULL && root -> right == NULL && d < res)
            res = d;
        
        minDepth(root -> left, d);
        minDepth(root -> right, d);
    }
};

  1. 广度优先搜索

思路和Binary Tree Level Order Traversal差不多，只不过这里要求返回的最大深度就是Binary Tree Level Order Traversal的最后vector的长度。因此只需要统计遍历的最低层数，即第一次遇到左右子树都为NULL的节点时的深度。

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution
{
public:
    int minDepth(TreeNode *root)
    {
        if(root == NULL)
            return 0;
        
        int res = 0;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
            ++ res;
            for(int i = 0, n = q.size(); i < n; ++ i)
            {
                TreeNode *p = q.front();
                q.pop();
                
                if(p -> left == NULL && p -> right == NULL)
                    return res;
                
                if(p -> left != NULL)
                    q.push(p -> left);
                if(p -> right != NULL)
                    q.push(p -> right);
            }
        }
        
        return res;
    }
};