leetcode解题: Minimum Depth of Binary Tree (111)

发表于 | 分类于

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.

解法1： BFS， O（N),

典型的用BFS的题，按层遍历，只要找到一个为叶子的节点，则当前记录的层数一定是最小层。 用一个queue来完成BFS。
C++
用到了queue 的push(), front() 和pop()

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
/**
 * 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 count = 0;
        if (!root) {
            return count;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            ++count;
            int k = q.size();
            for (int i = 0; i < k; ++i) {
                TreeNode* temp = q.front();
                q.pop();
                if (!temp->left && !temp->right) {
                    return count;
                }
                if (temp->left) {
                    q.push(temp->left);
                }
                if (temp->right) {
                    q.push(temp->right);
                }
            }
        }
        return count;
        
    }
};

Java

1

解法2： Recursive, Divide and Conquer, O(N)

一个数的最小层数是min（leftMin， rightMin） + 1, 用分治法和递归解决， code可以做到很简洁。
关于BFS和分治两者的复杂度分析，应该是一样的，参考九章的一个解答
C++

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
/**
 * 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) {
        
        if (!root) {
            return 0;
        }
        
        return helper(root);
    }
    
    int helper(TreeNode* root) {
        if (!root) {
            return INT_MAX;
        }
        
        if (!root->left && !root->right) {
            return 1;
        }
        
        return min(helper(root->left), helper(root->right)) + 1;
    }
};