从中序遍历和层序遍历构建二叉树

Question

从中序遍历和层序遍历构建二叉树

5

首先，我想声明这不是一个作业。我正在为一次面试做准备，遇到了这个问题。我猜我们可以跳过中序遍历和层序遍历的定义。:-)。

例如：

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

上述树的中序遍历和层次遍历如下： 5, 10, 20, 50, 51, 55, 60, 65, 70, 80 50, 10, 60, 5, 20, 55, 70, 51, 65, 80

我的想法是： (1) 遍历层次遍历数组，找出第一个出现在中序遍历数组中的元素。我们称这个元素为当前根节点。 (2) 找到当前根节点在中序遍历数组中的索引。中序遍历数组由该索引分隔。中序遍历数组的左侧是当前根节点的左子树，右侧是当前根节点的右子树。 (3) 更新中序遍历数组为其左侧，然后返回步骤1。 (4) 更新中序遍历数组为其右侧，然后返回步骤2。

以上述树为例。

(1) 5 is the first element appears in the in-order array. 

(2) [50 ...60] is the left sub-tree of 5 and [20 ... 80] is the right sub-tree of 5. 

(3) update the in-order array as [50 ... 60]

    (1) 10 is the first element appears in [50 10 60].

    (2) [50] is the left sub-tree of 10 and [60] is the right sub-tree of 10.

    (3) update ...

有人能帮我验证我的解决方案吗？如果能提供另一个解决方案，将不胜感激。

- Fihop

我认为这不是按顺序的，根据维基百科。 - Waleed Khan

1

我刚写了一个程序来验证它。对于中序遍历似乎没有问题。你能否给出示例树的中序遍历，让我再次检查一下？ - Fihop

1

我看起来错了。那看起来是正确的，抱歉。 - Waleed Khan

4个回答

0

            static tree MakeTreeFromInorderAndLevelOrder(int[] inorder,int[] lorder,int s,int n,int cnt1) {
    if(s>n || s>=inorder.length || n>=inorder.length || cnt1>=inorder.length) {
        return null;
    }
    int mIndex = Search(lorder[cnt1],inorder,s,n);
    tree t = new tree(lorder[cnt1]);

    cnt1 = 2*cnt1 + 1;
    t.left = MakeTreeFromInorderAndLevelOrder(inorder,lorder,s,mIndex-1,cnt1);
    //Boundary case
    if(cnt1<inorder.length && t.left==null) {
        t.right =   MakeTreeFromInorderAndLevelOrder(inorder,lorder,mIndex+1,n,cnt1);
    }
    else {
    cnt1 -=1;
    cnt1 /=2;
    cnt1 = 2*cnt1 + 2;
    t.right = MakeTreeFromInorderAndLevelOrder(inorder,lorder,mIndex+1,n,cnt1);
    //Boundary case
    if(t.right ==null && cnt1<inorder.length) {
        t.left = MakeTreeFromInorderAndLevelOrder(inorder,lorder,s,mIndex-1,cnt1);
    }
    }
    return t;
}

- badri.coder

你好，欢迎使用stackoverflow！但是我不认为这是对问题的答案。发帖人问的是有没有人能够验证他的算法正确性，而不是提供一个实现。如果您认为您的实现方式可以提供此验证，请在您的回答中解释一下。同时，请确保您的回答格式良好且易读。 - A. Donda

0

实际上，这个想法很简单，你只需要确保遍历顺序是否正确。例如，你想要进行中序遍历，你可以简单地想象：从左到右，从下到上。

遍历到左下角（5），然后遍历同一节点的右侧（20）。
从底部（10）向顶部（50）遍历。
在左侧做同样的事情。

对于层序遍历，你只需要逐步从上到下、从左到右遍历即可。

- JIANG

0

    node *construct (in, s, e, level) 
    {
      while (level order has element)
      {
          make the root by taking the first element from level order
          find the index of root->Val in in order.

          segregate the elements of left subtree and right subtree (make sure while 
          segregating from level order the order of element should be same)  call them
          leftLevel[] and rightLevel[]

          construct tree by recursively calling
          root->left  = construct(inorder,s, index-1, leftLevel);
          root->right = construct(inorder, index+1, e, rightlevel);
          return root;
      }
 }

使用哈希表进行元素分离将需要O(n)的时间，因此在平衡树中总体复杂度为O(nlogn)，但当树不平衡时，复杂度将变为O(n^2)。

- rgaut

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Srikar Appalaraju · Accepted Answer

我认为你正在走上正确的道路。下面是一个使用你的数据编写出来的工作代码。

/*
//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;
}