DS树--二叉树高度

题目描述

给出一棵二叉树，求它的高度。

注意，二叉树的层数是从1开始

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出

每行输出一个二叉树的高度

输入样例

1
AB0C00D00

输出样例

3

题解

#include <iostream>using namespace std;
#define MAX (int)1e5
string s;
int i;
int tree[100005];
int level;void create(int n) {i++;if (i > s.size() || s[i] == '0') return;tree[n] = s[i];create(n * 2 + 1);create(n * 2 + 2);
}void preCount(int n, int l) {level = max(level, l);if (n >= MAX || tree[n] == 0) return;preCount(n * 2 + 1, l + 1);preCount(n * 2 + 2, l + 1);
}int main() {int t;cin >> t;while (t--) {s.clear();level = 0;for (int ii = 0; ii < MAX; ii++) tree[ii] = 0;i = -1;cin >> s;create(0);preCount(0, 0);cout << level << endl;}return 0;
}