博客

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，如果根节点只有左子树（或者右子树）那么最小高度就是左子树（右子树）的最小高度。如果根节点既有左子树又有右子树，那最小高度就是子树高度最小的那个。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (root == NULL) return 0;
		if (root->left == NULL && root->right == NULL) return 1;
		if (root->left == NULL) return minDepth(root->right) + 1;
		if (root->right == NULL) return minDepth(root->left) + 1;
		int left = minDepth(root->left) + 1;
		int right = minDepth(root->right) + 1;
		return left < right ? left : right;
    }
};