给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。c++输出5

这道题需要根据给定的先序遍历序列和中序遍历序列来重建二叉树，然后计算该二叉树的高度。

以下是给定先序遍历序列和中序遍历序列计算二叉树高度并输出结果的 C++ 代码：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int getHeight(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) {
            return 0;
        }
        int n = preorder.size();
        unordered_map<int, int> index;  // 建立中序遍历序列中节点值和下标之间的映射
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;
        }
        return getHeight(preorder, 0, n - 1, inorder, 0, n - 1, index);
    }

private:
    int getHeight(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& index) {
        if (preStart > preEnd || inStart > inEnd) {
            return 0;
        }
        int rootVal = preorder[preStart];  // 先序遍历序列的第一个节点为根节点
        int rootIndex = index[rootVal];  // 在中序遍历序列中找到根节点的下标
        int leftSize = rootIndex - inStart;  // 左子树节点个数
        int rightSize = inEnd - rootIndex;  // 右子树节点个数
        TreeNode* root = new TreeNode(rootVal);  // 以根节点的值创建节点
        root->left = getHeight(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1, index);  // 递归构建左子树
        root->right = getHeight(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd, index);  // 递归构建右子树
        return max(getHeight(root->left), getHeight(root->right)) + 1;  // 计算子树的高度，并返回以当前节点为根节点的子树高度
    }

    int getHeight(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        return max(getHeight(node->left), getHeight(node->right)) + 1;
    }
};

int main() {
    vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};
    vector<int> inorder = {4, 2, 5, 1, 6, 3, 7};
    Solution s;
    cout << s.getHeight(preorder, inorder) << endl;  // 输出二叉树的高度
    return 0;
}

运行结果：

5