data-structures - 从有序遍历和层次遍历构造二叉树

首先，我想说这不是家庭作业。我正在准备面试，遇到这个问题。我猜我们可以传递in-order和level-order遍历的定义。 :-)。

例如:

      50
   /      \
 10        60
/  \       /  \
5   20    55    70
        /     /  \
      51     65    80

我的想法:



以上面的树为例。



谁能帮我验证我的解决方案？
非常感谢您再给一个。

最佳答案

我认为您在正确的轨道上。以下是我使用您的数据得出的有效代码。

/*
//construct a bst using inorder & levelorder traversals.
//inorder    - 5, 10, 20, 50, 51, 55, 60, 65, 70, 80
//levelorder - 50, 10, 60, 5, 20, 55, 70, 51, 65, 80
         50
      /      \
    10        60
   /  \       /  \
  5   20    55    70
            /     /  \
          51     65    80
 */
struct node *construct_bst3(int inorder[], int levelorder[], int in_start, int in_end)
{
    static int levelindex = 0;
    struct node *nnode = create_node(levelorder[levelindex++]);

    if (in_start == in_end)
        return nnode;

    //else find the index of this node in inorder array. left of it is left subtree, right of this index is right.
    int in_index = search_arr(inorder, in_start, in_end, nnode->data);

    //using in_index from inorder array, constructing left & right subtrees.
    nnode->left  = construct_bst3(inorder, levelorder, in_start, in_index-1);
    nnode->right = construct_bst3(inorder, levelorder, in_index+1, in_end);

    return nnode;
}