题解 | #从中序与后序遍历序列构造二叉树#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param inorder int整型一维数组 中序遍历序列
 * @param inorderLen int inorder数组长度
 * @param postorder int整型一维数组 后序遍历序列
 * @param postorderLen int postorder数组长度
 * @return TreeNode类
 */
// 在中序遍历序列中找到根节点的位置
int findPosition(int inorder[], int start, int end, int value) {
    for (int i = start; i <= end; i++) {
        if (inorder[i] == value) {
            return i;
        }
    }
    return -1;
}

// 从中序遍历和后序遍历序列构造二叉树
struct TreeNode* buildTreeHelper(int* inorder, int inorderStart, int inorderEnd,
                                 int* postorder, int postorderStart, int postorderEnd) {
    if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
        return NULL;
    }

    // 后序遍历序列的最后一个元素为当前子树的根节点
    int rootValue = postorder[postorderEnd];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootValue;
    root->left = NULL;
    root->right = NULL;

    // 在中序遍历序列中找到根节点的位置
    int rootIndex = findPosition(inorder, inorderStart, inorderEnd, rootValue);
    int leftTreeSize = rootIndex - inorderStart;

    // 递归构造左子树和右子树
    root->left = buildTreeHelper(inorder, inorderStart, rootIndex - 1, postorder,
                                 postorderStart, postorderStart + leftTreeSize - 1);
    root->right = buildTreeHelper(inorder, rootIndex + 1, inorderEnd, postorder,
                                  postorderStart + leftTreeSize, postorderEnd - 1);

    return root;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder,
                           int postorderSize) {
    return buildTreeHelper(inorder, 0, inorderSize - 1, postorder, 0,
                           postorderSize - 1);
}