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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

解法1：深度优先

思路：

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        int len = INT_MAX;
        minDepthCore(root, len, 1);
        return len;
    }
    void minDepthCore(TreeNode* root, int &len, int h){
        if(root != nullptr){
            minDepthCore(root->left, len, h + 1);
            minDepthCore(root->right, len, h + 1);  
            if(root->left == nullptr && root->right == nullptr){
                len = min(h, len);
            }
        }
    }
};

另一份AC代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!(root->left) &&!(root->right)) return 1;
        if(!(root->left)) return 1 + minDepth(root->right);
        else if(!(root->right)) return 1 + minDepth(root->left);
        else return 1 + min ( minDepth(root->left), minDepth(root->right));
    }
};

此题与二叉树的高度之间的关系。