【数据结构】二叉树——深度，节点个数，叶子节点个数

本文都以此数为例子

一、求二叉树的深度

我们若要求二叉树的深度，还是用递归来解决问题
我们采取的思路是，遍历二叉树若不为空就加 1
将一个节点的左右两节点遍历后对左右两节点深度进行比较，选取大的返回

//二叉树深度
int BTLevelDepth(BTNode* php)
{
	if (php == NULL)
	{
		return 0;
	}
	int left = BTLevelDepth(php->left);
	int right = BTLevelDepth(php->right);
	return left > right ? left + 1 : right + 1;
}

在代码中我们用 left 和 right 将左右两节点的深度进行保存
而不是在 return 中递归

return BTLevelDepth(php->left) > BTLevelDepth(php->right) ?
	BTLevelDepth(php->left) + 1 : BTLevelDepth(php->right) + 1;

因为如果我们不将左右保存下来，等进行比较时要递归一次，在选取大的返回时又要递归一次就会多出很多递归次数，使程序运行效率下降

二、二叉树节点个数

我们若要求二叉树节点的个数
我们采取的思路是，遍历二叉树
若不为空我们返回时加 1 ，
为空返回 0
返回值为左右两子树递归再加1

//二叉树节点个数
int BTSize(BTNode* pbt)
{
	if (pbt == NULL)
	{
		return 0;
	}

	return BTSize(pbt->left) + BTSize(pbt->right) + 1;
}

三、二叉树叶子节点个数

我们若要求二叉树叶子节点的个数
我们遍历二叉树
若遇到一个节点，其左右两节点都为空，我们就返回 1
返回值为左右两子树递归相加

// 二叉树叶子节点个数
int BTLeafSize(BTNode* php)
{
	if (php == NULL)
	{
		return 0;
	}
	if (php->left == NULL && php->right == NULL)
	{
		return 1;
	}

	return BTLeafSize(php->left) + BTLeafSize(php->right);
}