4019-平衡二叉树的高度的计算（C++，附思路）

描述

假设一棵平衡二叉树的每个结点都标明了平衡因子b，设计一个算法，求平衡二叉树的高度。

输入

多组数据，每组数据一行，为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当序列为“#”时，输入结束。

输出

每组数据输出一行，为平衡二叉树的高度。

输入样例 1 

110###0##
1110###0##10###
#

输出样例 1

3
4

思路：

这个题在oj系统里没有考虑平衡因子是-1的情况，极大地简化了题目?

关于平衡因子如果忘了的话可以即时看这篇，不用去翻ppt和课本了XD二叉树平衡因子_luzhensmart的专栏-CSDN博客_平衡因子https://blog.csdn.net/luzhensmart/article/details/85275100

二叉树的创建过程不说了，直接说遍历的思路吧。设置一个全局变量cnt用来计算高度，在遍历的时候，如果当前节点存在（这句很重要，不能丢）且平衡因子是1，说明左边更深一点，所以走左边；否则走右边，注意不管走哪边，cnt都要加一，因为起码这个节点是走过了的，得算一个高度。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<map>
using namespace std;

int cnt;
typedef struct BNode
{
	int bal;
	struct BNode* lchild, * rchild;
}*BTree, BNode;
void Create(BTree& bt, string s, int i)
{
	if (s[i] == '#')
		bt = NULL;
	else
	{
		bt = new BNode;
		bt->bal = s[i] - '0';
		Create(bt->lchild, s, ++i);
		Create(bt->rchild, s, ++i);
	}
}
void Traverse(BTree bt)
{
	if (bt)
	{
		cnt++;
		if (bt->bal == 1)
			Traverse(bt->lchild);
		else
			Traverse(bt->rchild);
	}
}
int main()
{
	string s;
	while (cin >> s && s != "#")
	{
		int i = -1;
		BTree bt = NULL;
		Create(bt, s, ++i);
		Traverse(bt);
		cout << cnt << endl;
		cnt = 0;
	}
	return 0;
}