题目描述
二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。
计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。
输入
测试次数t
每组测试数据一行，数组元素个数n，后跟n个字符，二叉树的数组存储。
输出
对每组测试数据，按后序遍历的顺序输出树中结点的平衡因子（测试数据没有空树）
输入样例1
2
6 ABC00D
24 ABCD0EF0000H00000000000I
输出样例1
B 0
D 0
C 1
A -1
D 0
B 1
I 0
H 1
E 2
F 0
C 2
A -2
AC代码
#include <bits/stdc++.h>
using namespace std;struct TreeNode {//树的节点char value;//当前的值int leftHeight;//左边的高度int rightHeight;//右边的高度int balanceFactor;//平衡因子
};int calculateHeight(vector<TreeNode>& tree, int index) {//传入整个树节点数组if (index >= tree.size() || tree[index].value == '0') {return 0; // 空节点高度为0}// 计算左子树和右子树的高度int leftHeight = calculateHeight(tree, 2 * index + 1);int rightHeight = calculateHeight(tree, 2 * index + 2);// 更新当前节点的高度和左右子树的高度tree[index].leftHeight = leftHeight;tree[index].rightHeight = rightHeight;tree[index].balanceFactor = leftHeight - rightHeight;return max(leftHeight, rightHeight) + 1; // 返回当前节点的高度
}void postOrderTraversal(const vector<TreeNode>& tree, int index, vector<string>& result) {if (index >= tree.size() || tree[index].value == '0') {return;//等于0的话就不push进去了，所以看不到0 0.}// 先递归遍历左子树，再右子树，最后处理当前节点postOrderTraversal(tree, 2 * index + 1, result);postOrderTraversal(tree, 2 * index + 2, result);result.push_back(string(1, tree[index].value) + " " + to_string(tree[index].balanceFactor));//string（1，tree。。。。）固定搭配，意思为形成一个一个长度的字符串。
}int main() {int t; // 测试次数cin >> t;while (t--) {int n;cin >> n;string treeData;//读取字符串cin >> treeData;vector<TreeNode> tree(n);//几个树的节点for (int i = 0; i < n; ++i) {tree[i].value = treeData[i];//每个都相应的赋值}// 计算每个节点的平衡因子calculateHeight(tree, 0);// 存储后序遍历的结果vector<string> result;postOrderTraversal(tree, 0, result);//后续遍历，从底部到顶部// 输出结果for (const string& res : result) {cout << res << endl;//循环输出结果}}return 0;
}
)