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

现在，这将返回到左侧调用 in [B]，所以leftChild = 0 = the abovein [B]。parentin将[B]自己设置为1（列表中的第二个节点，注意我们在之前的调用中提升了列表头 - 列表是全局的/通过引用传递）。它的左孩子将设置为您在上一步中计算的内容（上面的树）。你的树现在看起来像这样：

        1
      /
     0
  /     \
null   null

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

写/解释很多，但希望这能让你走上正轨。在纸上应该更容易理解。

于 2012-10-02T14:04:29.867 回答
0

如果你有一个排序的输入，那么创建一个二叉树很简单，因为它看起来因为在每个阶段递归地将数组除以左+中+右三部分并将左右附加到父/中，而回溯将创建二叉树（请注意，它不是我们构建的二叉搜索树，而是 BST，因为它是排序的输入的性质）。由于我们在回溯时构建树，每个元素（根+内部节点）最多可能被访问 2 次（分区时 1 次，回溯和分配子节点时其他时间），因此时间复杂度可能最多 O(2n) 或 O(n ） 一般来说。虽然看起来好像我们是从上到下构建树，因为我们执行递归，但实际上我们是自下而上构建树，因为节点在回溯时被构建并互连以形成子树。

这还有一个有趣的事实，即形成的树肯定是一棵完整的二叉树，除了节点从左到右填充的最后一层之外，所有层都完全填充。

当输入大小为 2 的幂时，可以获得完美（完整+平衡）二叉树，其中所有级别都完全填充，包括最后一级。

使用这种技术构建的平衡（abs（leftHeight）-abs（rightHeight）<=1）树可以是完美二叉树或完全二叉树，最后一层只有最左边的一个节点。

这适用于数组和链表。

于 2021-09-17T10:09:08.253 回答