比较一棵二叉树的终端节点到根节点的路径长度，路径长度为关键字之和，输出路径长度最短的终端节点。
输入：第一行输入一个整数 n, 表示结点的个数，第二行输入二叉树的中序遍历序列，第三行输入二叉树的后序遍历序列。

输出：路径长度最短的叶子节点的关键字。

用例：

输入：

7

3 2 1 4 5 7 6

3 1 2 5 6 7 4

输出：

1

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

// 定义二叉树节点结构
struct TreeNode {
    int key;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 构建二叉树
static struct TreeNode* BuildTree(int* inorder, int* postorder, int inStart, int inEnd, int postStart, int postEnd)
{
    // 终止条件：中序遍历或后序遍历的起始位置超过结束位置
    if ((inStart > inEnd) || (postStart > postEnd)) {
        return NULL;
    }

    // 创建根节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (!root) {
        return NULL; // 内存分配失败
    }

    // 根据后序遍历确定根节点值
    root->key = postorder[postEnd];

    // 在中序遍历中找到根节点的位置
    int rootIndex;
    for (rootIndex = inStart; rootIndex <= inEnd; ++rootIndex) {
        if (inorder[rootIndex] == root->key) {
            break;
        }
    }

    // 计算左子树和右子树的节点数量
    int leftSize = rootIndex - inStart;
    int rightSize = inEnd - rootIndex;

    // 递归构建左子树和右子树
    root->left = BuildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
    root->right = BuildTree(inorder, postorder, rootIndex + 1, inEnd, postEnd - rightSize, postEnd - 1);

    return root;
}


// 找到路径长度最短的终端节点
static void FindShortestPathLeaf(struct TreeNode* root, int* shortestPath, int* shortestLeaf, int pathLength)
{
    if (root == NULL) {
        return;
    }

    // 当前节点为叶子节点时
    if ((root->left == NULL) && (root->right == NULL)) {

        // 更新最短路径和对应的叶子节点值
        if (*shortestPath == -1 || pathLength + root->key < *shortestPath) {
            *shortestPath = pathLength + root->key;
            *shortestLeaf = root->key;
        }
        return;
    }

    // 递归查找左右子树
    FindShortestPathLeaf(root->left, shortestPath, shortestLeaf, pathLength + root->key);
    FindShortestPathLeaf(root->right, shortestPath, shortestLeaf, pathLength + root->key);
}

int main()
{
    int n;
    printf("Enter the number of nodes: ");
    scanf_s("%d", &n);

    int* inorder = (int*)malloc(n * sizeof(int));
    int* postorder = (int*)malloc(n * sizeof(int));
    if (!inorder || !postorder) {
        return -1; // 内存分配失败
    }

    // 输入中序遍历序列
    printf("Enter the inorder traversal sequence: ");
    for (int i = 0; i < n; ++i) {
        scanf_s("%d", &inorder[i]);
    }

    // 输入后序遍历序列
    printf("Enter the postorder traversal sequence: ");
    for (int i = 0; i < n; ++i) {
        scanf_s("%d", &postorder[i]);
    }

    // 构建二叉树
    struct TreeNode* root = BuildTree(inorder, postorder, 0, n - 1, 0, n - 1);

    int shortestPath = -1;
    int shortestLeaf = -1;

    // 寻找路径长度最短的终端节点
    FindShortestPathLeaf(root, &shortestPath, &shortestLeaf, 0);

    // 输出结果
    printf("The terminal node with the shortest path length is: %d\n", shortestLeaf);

    // 释放动态分配的内存
    free(inorder);
    free(postorder);

    return 0;
}