[C ++每日问题]计算二叉搜索树的高度

给出一个需要计算其高度的二叉搜索树，每个二叉搜索树都将遍历前置和中阶.

例如: 对于二叉搜索树，一阶遍历为: 16、10、4、15、23；中间遍历是4、10、15、16、23，则其高度是2（假设空树的高度是-1，只有根节点的数字高度是0）

在第一行输入测试用例的数量.

对于每个测试用例，

第一行是节点数n，第二行是键值的一阶遍历，第三行是键值的中阶遍历

对于每个测试用例，使用一行输出树的高度

2

3

4 5 6

4 5 6

5

6 4 8 9 10

4 6 8 9 10

2

3

首先，基于二叉树的遍历特性

可以推断出首先遍历的第一个元素是二叉树的根节点.

在中间遍历中，如果找到根节点，则根节点的左节点是左子树节点，右节点是右子树节点.

为便于说明，请设置一些变量

如果根节点具有左子树，则在第一个遍历中具有下标root +1的节点是左子树的根节点，而[left，pos）是左子树的所有节点.

下标为root + pos-left +1的节点是上次遍历的右子树的根节点，[pos + 1，right）是右子树的所有节点.

了解左右子树的元素，并找到两个子树的根节点，以相同的方式在左右子树中找到左右子树二叉排序树算法，从而可以确定递归唯一的二叉树

这个问题只需要树的高度，那么我们可以认为，如果一棵树具有左或右子树，则该树的高度+ 1.

上面的描述可能不是很准确，例如，更清晰一些，具有9个节点的二叉树

根树

根节点为5；

左子树的根节点为2，一阶遍历的下标为root + 1 = 1；所有节点均为1 2 3 4二叉排序树算法，中阶遍历的下标范围为[0，4）.

右子树的根节点为8，一阶遍历的下标为root + pos-left +1 = 5;所有节点均为6 7 8 9，中阶遍历的下标范围为[5，9）.

根树的左子树

根节点是2；

左子树的左子树的根节点为1，一阶遍历的下标为root + 1 = 2；所有节点均为1，中阶遍历的下标范围为[0，1）.

左子树的右子树的根节点为4，一阶遍历的下标为root + pos-left + 1 = 3;所有节点均为3 4，中阶遍历的下标范围为[二十四].

根树的左右子树

根节点为8；

左子树的左子树的根节点为7，一阶遍历的下标为root + 1 = 6；所有节点均为6 7，中阶遍历的下标范围为[5，7）.

左子树的右子树的根节点为9，一阶遍历的下标为root + pos-left + 1 = 8;所有节点均为9，中阶遍历的下标范围为[8，9）.

左子树的左右子树，右子树的左右子树以相同的方式递归，因此不再列出.

#include <cstdio>
int preorder[1000001];  // 先序遍历
int inorder[1000001];  // 中序遍历
int height = 0;  // 树的高度
void findHeight(int root, int left, int right, int h);
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        height = -1;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d", preorder + i);
        for (int i = 0; i < n; ++i)
            scanf("%d", inorder + i);
        findHeight(0, 0, n, 0);
        printf("%d\n", height);
    }
    return 0;
}
void findHeight(int root, int left, int right, int h) {
    if (left >= right) return;  // 判断是否为空树
    int pivot = preorder[root];
    int pos = left;
    if (h > height) height = h;  // 更新树的高度
    while (pos < right && inorder[pos] != pivot) pos++;  // 找根结点在中序遍历中的下标
    // 递归遍历左子树
    if (left < pos) findHeight(root + 1, left, pos, h + 1);
    // 递归遍历右子树
    if (pos + 1 < right) findHeight(root + pos - left + 1, pos + 1, right, h + 1);
}

以上所有，如果有错误，请指出我会及时更改它们.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-224271-1.html