一：分治算法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

二：基本思想

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

三：解题步骤

分解，将要解决的问题划分成若干规模较小的同类问题；
求解，当子问题划分得足够小时，用较简单的方法解决；
合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

四：二叉树应用

4.1 二叉树节点个数

思路：

空树，最小子规模问题，节点个数返回0；
非空，左子树节点个数 + 右子树节点个数 + 1(自己)；

代码示例：

//思想：分治
int BTreeSize(BTNode* root){
	if (root == NULL){
		return 0;
	}
	return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

4.2 叶子节点个数

思路：分治

//分治 计算叶子节点个数
int BTreeLeafSize(BTNode* root){
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

4.3 二叉树深度

思路：分治

int BTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftDepth = BTreeDepth(root->left);
	int rightDepth = BTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

4.4 二叉树第k层节点个数

思路：分治思想计算第k - 1层加上根节点

int BTreeKLevelSize(BTNode* root, int k){
	assert(k >= 1);

	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BTreeKLevelSize(root->left, k - 1)
		+ BTreeKLevelSize(root->right, k - 1);

}