计算二叉树的高度/深度

计算二叉树的高度/深度

默认根结点层次为1。如果为空树，高度为0；如果不是空树，树的高度就是左右子树中高度的较大者+1（+1是包含当前层次的高度）。

//计算树的高度
int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//左右子树中的较大者+1返回
	return TreeHeight(root->left) > TreeHeight(root->right) ?
		TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

但是上面的程序在每次比较完左子树与右子树的高度之后，直接就把已经得到的结果抛弃了，在返回结果时还要重新再同故宫递归重新计算一次高度，造成了非常大的性能浪费，所以需要再定义两个变量来保存已经得到的结果。

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//左右子树中的较大者+1返回
	int LeftHeight = TreeHeight(root->left);
	int RightHeight = TreeHeight(root->right);
	return LeftHeight > RightHeight ?
		LeftHeight + 1 : RightHeight + 1;
}