求二叉树节点的个数——后序遍历

之前我们已经学习了二叉树前中后序的遍历，在次基础上我们利用遍历来求二叉树的节点个数

利用变量来计数：

int BinaryTreeSize(BTNode* root)
{
	int size = 0;
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		size++;
	}
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是这样的递归遍历之后最后返回的size=0;
因为：

改进：那么我们是不是可以把变量size利用static把变量size放到静态区

int BinaryTreeSize(BTNode* root)
{
	static int size = 0;
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		size++;
	}
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);

	return size;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这样最后的size的确是节点的个数，但是在我们之后再次调用这个求节点个数的函数的时候，size并不会从新从0开是计数，所以得出的结果就是错误的，

接着改进：
我们把size放到函数外，作为一个全局变量来计数

int size = 0;
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		size++;
	}
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);

	return size;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结果是正确的，但是当再次调用这个函数的时候要在之前加上size=0；才可以

所以还需要改进：
既然是求二叉树的节点数，那么去我们是否可以利用二叉树的遍历来求呢？

nt BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;

}
1
2
3
4
5

利用二叉树后序遍历的原理轻松解决：