leetcode做题笔记106. 从中序与后序遍历序列构造二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记106. 从中序与后序遍历序列构造二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路一：递归

struct TreeNode* createTreeNode(int val) {
    struct TreeNode* ret = malloc(sizeof(struct TreeNode));
    ret->val = val;
    ret->left = ret->right = NULL;
    return ret;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    if (postorderSize == 0) {
        return NULL;
    }
    struct TreeNode* root = createTreeNode(postorder[postorderSize - 1]);
    struct TreeNode** s = malloc(sizeof(struct TreeNode*) * 10001);
    int top = 0;
    s[top++] = root;
    int inorderIndex = inorderSize - 1;
    for (int i = postorderSize - 2; i >= 0; i--) {
        int postorderVal = postorder[i];
        struct TreeNode* node = s[top - 1];
        if (node->val != inorder[inorderIndex]) {
            node->right = createTreeNode(postorderVal);
            s[top++] = node->right;
        } else {
            while (top > 0 && s[top - 1]->val == inorder[inorderIndex]) {
                node = s[--top];
                inorderIndex--;
            }
            node->left = createTreeNode(postorderVal);
            s[top++] = node->left;
        }
    }
    return root;
}