从中序和后序遍历构造二叉树

Question

我遇到了一个我真正感兴趣的问题，但我不确定我是否完全理解如何完成手头的任务:设计一种算法，从两个 n 长序列构造二叉树，已知是同一二叉树的中序和后序遍历。

到目前为止我已经完成了这么多。下面是到目前为止我的(相关)代码，但是我也希望能够识别不存在二叉树的序列。我不知道如何检查这一点。有人可以给我一个正确的方向吗？

node* build_tree(int in[], int inStart, int inEnd,
                 int post[], int postStart, int postEnd) {
    if(inStart > inEnd || postStart > postEnd)
        return NULL;

    int rootValue = post[postEnd];
    node *tNode = new_node(rootValue);

    // find the index of this node in in-order traversal
    int inIndex = search(in, inStart, inEnd, rootValue);

    // Using index in in-order traversal, construct left and right subtrees
    tNode->left = build_tree(in, inStart, inIndex-1, post, postStart, postStart+inIndex-(inStart+1));
    tNode->right = build_tree(in, inIndex+1, inEnd, post, postStart + inIndex - inStart, postEnd - 1);

    return tNode;
}

// Function to find index of value in arr[start...end]
// The function assumes that value is present in in[]
int search(int arr[], int start, int end, int value) {
    int i;
    for(i = start; i < end; i++) {
        if(arr[i] == value)
            return i;
    }

    return i;
}

// function that allocates a new node with the
// given data and NULL left and right pointers
node* new_node(int data) {
    node* n = (node*)malloc(sizeof(node));
    n->data = data;
    n->left = NULL;
    n->right = NULL;

    return n;
}

Answer 1

据我所知，当 时，二叉树对于给定序列是不可能的，

1) 两个序列长度不同 -- 我们可以检查数组长度

2) 中序序列中查找后序值失败 -- 搜索函数应修改为在搜索失败时返回负值，而不是返回 i(在 for 循环之后)

3) 给定的序列不代表同一棵树的后序和中序 -- 按照 Gene 的建议遍历树并检查序列