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 ...

ソリューションの検証を手伝ってくれる人はいますか? そして、別のものを与えるなら本当に感謝します。

4

4 に答える 4

2

あなたは正しい軌道に乗っていると思います。以下は、あなたのデータを使用して作成した作業コードです。

/*
//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;
}
于 2013-08-06T16:59:40.210 に答える
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;
}
于 2014-02-15T16:03:33.187 に答える
0

実際、考え方は単純で、トラバース シーケンスが正しいかどうかを確認するだけです。たとえば、順序通りに走査したい場合は、単純に次のように考えることができます: 左から右へ、下から上へ。

  1. 同じノードの左下 (5) にトラバースしてから、右 (20) にトラバースします。

  2. 下（10）から上（50）までトラバースします。

  3. 左も同じようにします。

レバーの順番は、上から下へ、左から右へ、段階的にトラバースするだけです。

于 2013-04-03T00:20:37.163 に答える
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) になります。

于 2014-09-25T00:56:21.250 に答える