爱悠闲 > Minimum Depth of Binary Tree -- 二叉树的最小深度 DFS 加剪枝

Minimum Depth of Binary Tree -- 二叉树的最小深度 DFS 加剪枝

分类: leetcode  |  作者: skyoceanlover 相关  |  发布日期 : 2015-11-27  |  热度 : 1174°

题目:

链接

解答:

深搜,剪枝搜索过程中深度大于最小值的情况。

代码:

class Solution {
public:
	int minDepth(TreeNode *root) {
		if (root == NULL)
			return 0;
		int min = INT_MAX;
		search(root, 1, min);
		return min;

	}
	void search(TreeNode *root, int deep, int &min)
	{
		if (deep > min)
			return;
		if (root->left == NULL && root->right == NULL)
		{
			if (deep < min)
				min = deep;
		}
		else
		{
			if (root->left != NULL)
				search(root->left, deep + 1, min);
			if (root->right != NULL)
				search(root->right, deep + 1, min);
		}
	}
};