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],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

// Recursion
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    if (!root->left) return minDepth(root->right) + 1;
    if (!root->right) return minDepth(root->left) + 1;
    return min(minDepth(root->left), minDepth(root->right)) + 1;
}

// Recursion
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    int l_depth = minDepth(root->left), r_depth = minDepth(root->right);
    if (l_depth == 0 || r_depth == 0) return (l_depth ? l_depth : r_depth) + 1;
    else return min(l_depth, r_depth) + 1;
}

// Recursion
void helper(TreeNode* root, int cur, int& res) {
    if (!root) return;
    ++cur;
    if (!root->left && !root->right) { // only update when the node is leaf
        res = min(res, cur);
    }
    helper(root->left, cur, res);
    helper(root->right, cur, res);
}
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    int res = 1e8, cur = 0;
    helper(root, cur, res);
    return res == 1e8 ? 0 : res;
}

// Iteration (Level Order Traversal)
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int res = 0;
    while (!q.empty()) {
        ++res;
        int n = q.size();
        for (int i = 0; i < n; ++i) {
            TreeNode* cur = q.front(); q.pop();
            if (!cur->left && !cur->right) return res;
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return -1;
}