111

111. Minimum Depth of Binary Tree (Easy)

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 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

 

Constraints:

• The number of nodes in the tree is in the range [0, 105].
• -1000 <= Node.val <= 1000

Related Topics:
Tree, Depth-first Search, Breadth-first Search

Similar Questions:

• Binary Tree Level Order Traversal (Medium)
• Maximum Depth of Binary Tree (Easy)

Solution 1. BFS

// OJ: https://leetcode.com/problems/minimum-depth-of-binary-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int ans = 1;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto node = q.front();
                q.pop();
                if (!node->left && !node->right) return ans;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ++ans;
        }
        return -1;
    }
};

Solution 2. DFS

// OJ: https://leetcode.com/problems/minimum-depth-of-binary-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        int d = INT_MAX;
        if (root->left) d = minDepth(root->left);
        if (root->right) d = min(d, minDepth(root->right));
        return 1 + d;
    }
};