还原二叉树

给定一棵二叉树的前序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数 n（≤50），为树中结点总数。随后 2 行先后给出前序和中序遍历序列，均是长度为 n 的不包含重复英文字母（区别大小写）的字符串。

输出格式:

输出为一个整数，即该二叉树的高度。

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
    char data;//储存节点的数据
    struct TreeNode *left;//指向左子树
    struct TreeNode *right;//指向右子树
} TreeNode;


/**
 * 
 * 计算二叉树的高度
*/
int getHeight(TreeNode *root) {
    if (root == NULL) {
        return 0;//二叉树为空，则返回0
    } else {
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

/**
 * 
 * 构建二叉树
*/
TreeNode* buildTree(char *preorder, char *inorder, int size) {
    if (size <= 0) {
        return NULL;
    }
    
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = *preorder;
    root->left = root->right = NULL;
    
    char *rootInOrder = inorder;
    while (*rootInOrder != *preorder) {
        rootInOrder++;
    }
    
    int leftSize = rootInOrder - inorder;
    
    root->left = buildTree(preorder + 1, inorder, leftSize);
    root->right = buildTree(preorder + 1 + leftSize, rootInOrder + 1, size - leftSize - 1);
    
    return root;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char preorder[n+1];
    char inorder[n+1];
    
    scanf("%s", preorder);
    scanf("%s", inorder);
    
    TreeNode *root = buildTree(preorder, inorder, n);
    
    int height = getHeight(root);
    printf("%d\n", height);
    
    return 0;
}