如何使用{pre,in,post}顺序遍历结果重建BST

Question

我们知道预订,有序和后期遍历.什么算法会重建BST？

Answer 1

因为它是BST,in-order可以从排序pre-order或post-order<1>.实际上,只有...... pre-order或者post-order只是......

<1>如果你知道比较函数是什么

从pre-order和in-order构建二叉树

BT createBT(int* preOrder, int* inOrder, int len)
{
    int i;
    BT tree;
    if(len <= 0)
        return NULL;
    tree = new BTNode;
    t->data = *preOrder;
    for(i = 0; i < len; i++)
        if(*(inOrder + i) == *preOrder)
            break;
    tree->left = createBT(preOrder + 1, inOrder, i);
    tree->right = createBT(preOrder + i + 1, inOrder + i + 1, len - i - 1);
    return tree;
}

这背后的理由:

在预订中,第一个节点是根.在有序中找到根.然后树可以分为左和右.递归地做.

类似于post-order和in-order.