LeetCode 111. Minimum Depth of Binary Tree

LeetCode Minimum Depth of Binary Tree

Description:

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.

---

分析：

这道题同样需要注意一下题意，和1004求二叉树的最大深度有一点区别，这里要注意只有两层树时，当左子树或者右子树为NULL时，最小深度并不是1（只有根节点），而是需要递归判断另外一棵不为空的子树，因为题意是要根节点到任意结点的最小深度。
当左右子树都不为NULL时，分别递归求解左右子树minDepth(root->left) minDepth(root->right)，然后返回其中的最小值。

代码如下：

#include <iostream>
using namespace std;
/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	int minDepth(TreeNode* root) {
		if (root == NULL) {
			return 0;
		}
		else if (root->left == NULL && root->right != NULL) {
			return minDepth(root->right) + 1;
		}
		else if (root->left != NULL && root->right == NULL) {
			return minDepth(root->left) + 1;
		}
		else {
			int leftDepth = minDepth(root->left) + 1;
			int rightDepth = minDepth(root->right) + 1;
			return leftDepth < rightDepth ? leftDepth : rightDepth;
		}
	}
};
// 构造二叉树
int TreeNodeCreate(TreeNode* &tree) {
	int val;
	cin >> val;
	if (val < 0) // 小于0表示空节点
		tree = NULL;
	else {
		tree = new TreeNode(val); // 创建根节点
		tree->val = val;
		TreeNodeCreate(tree->left); // 创建左子树
		TreeNodeCreate(tree->right);// 创建右子树
	}
	return 0;
}
int main() {
	Solution s;
	TreeNode* tree;
	TreeNodeCreate(tree);
	cout << s.minDepth(tree) << endl;
	return 0;
}