已知前序中序遍历，求二叉树的高度

此题所涉及的建树详细请见我上一篇博文，二叉树的构造，这种构造方法简单容易理解 

此处求树高采用的是递归求解，对每一层最长树加上当前节点的高度 

 
#include 
#include 
#include 
using namespace std;
 
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : val(val), left(nullptr), right(nullptr) {}
};
 
// 根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTree(string& preorder, string& inorder,
                    int preStart, int inStart, int inEnd,
                    unordered_map<char, int>& indexMap) {
    if (preStart > preorder.size() - 1 || inStart > inEnd) {
        return nullptr;
    }
 
    char rootValue = preorder[preStart];
    TreeNode* root = new TreeNode(rootValue);
    int rootIndex = indexMap[rootValue];
 
    root->left = buildTree(preorder, inorder, preStart + 1, inStart, rootIndex - 1, indexMap);
    root->right = buildTree(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, indexMap);
 
    return root;
}
 
// 计算二叉树的高度
int getHeight(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
 
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
 
    return max(leftHeight, rightHeight) + 1;
}
 
int main() {
    int n;
    while (cin >> n) {
        string preorder, inorder;
        cin >> preorder >> inorder;
 
        unordered_map<char, int> indexMap;
        for (int i = 0; i < n; ++i) {
            indexMap[inorder[i]] = i;
        }
 
        TreeNode* root = buildTree(preorder, inorder, 0, 0, n - 1, indexMap);
        int height = getHeight(root);
 
        cout << height << endl;
    }
    return 0;
}