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

思路

如果這麼求的話，沒有左孩子的分支會算為最短深度。

所以，如果左子樹為空，右子樹不為空，說明最小深度是 1 + 右子樹的深度。

反之，右子樹為空，左子樹不為空，最小深度是 1 + 左子樹的深度。 最後如果左右子樹都不為空，返回左右子樹深度最小值 + 1 。

Solution (recursive)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if ( root == NULL ) return 0;
        int leftDepth = minDepth( root -> left );
        int rightDepth = minDepth( root -> right );
        if ( root -> left == NULL && root -> right != NULL ) {
            return 1 + rightDepth;
        }

        if ( root -> right == NULL && root -> left != NULL ) {
            return 1 + leftDepth;
        }

        int result = 1 + min( leftDepth, rightDepth );
        return result;
    }
};

Solution (bfs)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        queue <TreeNode*> que;
        if ( root == NULL ) return 0;
        else que.push(root);
        int depth = 0;
        while ( !que.empty() ) {
            int que_size = que.size();
            depth++;
            for ( int j = 0; j < que_size; j++ ) {
                TreeNode * node = que.front();
                que.pop();
                if ( node -> left != NULL ) que.push( node -> left );
                if ( node -> right != NULL )  que.push( node -> right );
                if ( node -> left == NULL && node -> right == NULL ) return depth; 
            }

        }
        return -1;
    }
};