题目描述
给出一棵二叉树，求它的高度。二叉树的创建采用前面实验的方法。
注意，二叉树的层数是从1开始
输入
第一行输入一个整数t，表示有t个二叉树
第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行
输出
每行输出一个二叉树的高度
输入样例1
1 AB0C00D00
输出样例1
3
思路分析
首先把树给建立起来，递归建立树的每个节点，先建立数据，再递归建立左子树，然后递归建立右子树，递归结束的条件是到了字符串末尾或者遇到字符0。
我一开始的想法是，计算出每个节点的深度，然后找出最大的深度，后来出了点问题，在我的学长的光芒下，用三行代码算出了树的高度。
递归求解树的高度：
如果节点为空，返回0，否则返回左子树和右子树的高度的最大者加一。
膜拜大佬。
AC代码
代码语言：javascript复制#include <iostream>
#include <string>
using namespace std;
class BiTreeNode {
public:
char data; //数据域
BiTreeNode *leftChild, *rightChild; //左右子树指针
BiTreeNode():leftChild(NULL), rightChild(NULL){}
~BiTreeNode() {}
};
class BiTree {
private:
BiTreeNode *root; //根结点指针
string sTree; //建树字符串
int pos; //标识建树字符串的当前字符位置
BiTreeNode * CreateTree();//建树私有函数
public:
BiTree():root(NULL) {};
void Create(string vArray); //建树公有接口，参数是特定的先序遍历字符串
int CountHeight(BiTreeNode*T) {
if(T==NULL)
return 0;
return max(CountHeight(T->leftChild), CountHeight(T->rightChild)) 1;
}
void Show(){
cout << CountHeight(root) << endl;
}
};
void BiTree::Create(string vArray)
{ pos=0;
sTree.assign(vArray); //把参数保存到内部字符串
root = CreateTree(); //建树成功后root指向根结点
}
BiTreeNode* BiTree::CreateTree() {
if(pos==sTree.size()||sTree[pos]=='0'){
pos ;
return NULL;
}
BiTreeNode*T=new BiTreeNode();
T->data=sTree[pos ];
T->leftChild=CreateTree();
T->rightChild=CreateTree();
return T;
}
int main()
{ int t;
string vArray;
cin>>t;
while(t--)
{ cin>>vArray;
BiTree myTree;
myTree.Create(vArray);
myTree.Show();
}
return 0;
}
