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.

http://www.lintcode.com/en/problem/minimum-depth-of-binary-tree/

Discussion

跟maximum depth of binary tree非常像。 递归很简单，左右子树的最小depth加1.要注意左子树或者右子树为空的情况，因为题目要求是根到叶子的距离。 非递归的写法就是level order traversal。

Solution

递归。O(n) runtime, O(log n) space

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int minDepth(TreeNode *root) {
        // write your code here
        if(root == NULL) return 0;
        if(root->left == NULL) {
            return minDepth(root->right)+1;
        }
        if(root->right == NULL) {
            return minDepth(root->left) + 1;
        }
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

level order traversal不写了，当遇到左右child都为空的时候就退出。

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int minDepth(TreeNode *root) {
        // write your code here
        if(root == nullptr) {
            return 0;
        }
        queue<TreeNode *> myque;
        myque.push(root);
        int min_len = 1;
        while(myque.empty() == false) {
            int len = myque.size();
            bool has_leaf = false;
            for(int i=0; i<len; i++) {
                TreeNode *cur = myque.front();
                myque.pop();
                if(cur->left == NULL && cur->right == NULL) {
                    has_leaf = true;
                    break;
                }
                if(cur->left != NULL) {
                    myque.push(cur->left);
                }
                if(cur->right != NULL) {
                    myque.push(cur->right);
                }
            }
            if(has_leaf == true) {
                break;
            }
            min_len++;
        }
        return min_len;
    }
};