如何构建二进制搜索树自下而上

Question

给定一个排序数组,很容易以自上而下的方式从中可视化BST.例如,如果数组是[1,2,3,4,5,6,7],我们可以看到根将是中间元素,即4.在它的左边会有一个子树,其根是左侧数组切片的中间4,即2.同样地,它也会在右边相似.

我们如何通过自下而上的方法来构建BST？基本上我试图理解从排序链表中构造BST的算法,该列表采用O(N)自下而上的方式,并O(Nlog N)以自上而下的方式.所以我需要了解它是如何构建自下而上的.

Answer 1

请考虑: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].将parent在[B]将自身设置为1(在列表中的第二个节点,请注意,我们在以前的调用先进的表头-名单是全球/按引用传递).它的左子项将设置为您在上一步中计算的内容(上面的树).你的树现在看起来像这样:

        1
      /
     0
  /     \
null   null

列表再次提前,指向2.sortedListToBST(list, 2, 3)将进行递归调用[B],这将触发多个递归调用.

写/解释很多,但希望这能让你走上正轨.它应该更容易在纸上进行.