题目

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.

分析

求二叉树的最小深度：根节点到最近叶子节点的路径长度。

同样采用递归的思想：

1. 当根节点为空，返回0；
2. 当根节点为唯一的二叉树节点时，返回1；
3. 否则，求解并返回 最小(非空，保证最终到达叶节点)左右子树深度 + 1；

AC代码

class Solution {

public:

    int minDepth(TreeNode* root) {

        if (!root)

            return 0;

        //独立的根节点

        else if (!root->left && !root->right)

            return 1;

        else{

            int left_depth, right_depth;

            if (root->left)

                left_depth = minDepth(root->left);

            else

                left_depth = INT_MAX;

            if (root->right)

                right_depth = minDepth(root->right);

            else

                right_depth = INT_MAX;

            return min(left_depth, right_depth) + 1;

        }

    }

};

GitHub测试程序源码