FXTi's blog
0%

minimum-depth-of-binary-tree

Posted on Edited on

Minimum Depth of Binary Tree – LeetCode 111

Problem

Description

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.

Answer

Original

Code

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

思路

私以为这道题目用BFS更为直观，因为是求最短路径。这里需要注意的是寻找的是left和right都为nullptr的节点，一旦发现就证明找到了最短路径。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$6$ ms，排名$44.70\%$

Better

思路

LeetCode论坛上看到的DFS解，写的相当漂亮，一旦发现left和right中任一为nullptr就继续求另一支的最近路径，以此必定会遍历到目标节点。更妙的是最后的情况判断和目标节点的判断合二为一。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$6$ ms，排名$44.70\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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;
        if(!root->left) return 1 + minDepth(root->right);
        if(!root->right) return 1 + minDepth(root->left);
        return 1+min(minDepth(root->left),minDepth(root->right));
    }
};

耗时$6$ ms，排名$44.70\%$