6

並べ替えられた配列があれば、そこから BST をトップダウンで視覚化するのは非常に簡単です。たとえば、配列が の場合[1,2,3,4,5,6,7]、ルートが中央の要素、つまり になることがわかります4。その左側には、ルートが の左側にある配列スライスの中央、つまり のサブツリーがあり4ます2。右も同様です。

BST を構築するためのボトムアップ アプローチでこの視覚化を行うにはどうすればよいでしょうか? 基本的に、ソートされたリンクリストから BST を構築するアルゴリズムを理解しようとしています。これはO(N)、ボトムアップ方式とO(Nlog N)トップダウン方式で行われます。そのため、ボトムアップがどのように構築されるかを理解する必要があります。

4

2 に答える 2

8

検討してください：http：//www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}

再帰呼び出しのいくつかを書き出しましょう：

0 1 2 3 4 5 6 7 8 -> sortedListToBST(list, 0, 3) [A]
0 1 2 3           -> sortedListToBST(list, 0, 0) [B]
0                 -> sortedListToBST(list, 0, -1) [C]
*                 -> NULL [D]

[D]を返しNULLます。

ここで、に[C]とleftChild = NULL（parent = 0リストの最初のノード）があります。親の左の子はNULLになり、リストが進行します。[C]次に、を呼び出しますsortedListToBst(1, 0)。これはに戻ります。NULLしたがって、の右の子parentもになりますNULL。これまでのツリーは次のようになります。

        0
     /     \
  null     null

さて、これはの左の呼び出しに返されます[B]のでleftChild = 0 = the above、[B]。parentin[B]はそれ自体をに設定します（1リストの2番目のノード、前の呼び出しでリストヘッドを進めたことに注意してください-リストはグローバル/参照によって渡されます）。その左の子は、前のステップ（上のツリー）で計算したものに設定されます。これで、ツリーは次のようになります。

        1
      /
     0
  /     \
null   null

リストは再び進み、を指してい2ます。から再帰呼び出しsortedListToBST(list, 2, 3)が行われ[B]、複数の再帰呼び出しがトリガーされます。

書く/説明することはたくさんありますが、うまくいけば、これはあなたを正しい軌道に乗せることができます。紙の上でフォローする方が簡単なはずです。

于 2012-10-02T14:04:29.867 に答える