algorithm - 从排序链表构造 BST 的迭代解决方案

Question

我想从一个排序的链表创建一个 BST。我已经递归地解决了这个问题，但想知道如何在不改变问题复杂性的情况下为此编写一个迭代解决方案。

[编辑]

注意:我不想实现自己的堆栈。

[编辑2]

递归调用自身的函数是f。伪代码如下。从 main

使用头指针调用 f

node * f(int start_index, int end_index, node *ptr) {
     if ( start>end) return NULL
     middle_index = start_index + (end_index-start_index)/2
     node *l_child = f(start_index, middle_index-1, ptr)
     initialize parent with ptr's value 
     parent->left = l_child
     ptr = ptr->next
     parent->right = f(middle_index+1, end, ptr)
     return parent
}

Answer 1

提前假设你希望它像这样，大致:

    _______
   /       \
  / \     / \
 /   \   /   \
/ \ / \ / \ /
1 2 3 4 5 6 7

然后你就可以显式求解结构了。在这种情况下，对于某个整数 N 的长度 L<2^N 的列表，并假设您创建了所有节点并将一些叶子保留为“空”(或者甚至不构建这些节点) ，树中的节点总数等于 (2*2^N)-1。您的节点看起来像:

    12345678
   /       \
  1234    5678
  / \     / \
 12  34  56  78
/ \ / \ / \ / \
1 2 3 4 5 6 7

我提到了节点的大小，因为它应该让我们深入了解如何进行:应该有一些方法来枚举 {1,2}->12, {3,4}->34, {12,34}->1234, ...。一种方法是从底部开始对节点进行分组。例如，我们可以在 N (3) 遍中执行此操作:

step 1:    1  2   3  4    5  6   7
step 2:   (1  2) (3  4)  (5  6) (7   )
step 3:  ((1  2) (3  4))((5  6) (7   ))
step 4: (((1  2) (3  4))((5  6) (7   )))

另一种方法是在我们对更高级别的节点进行分组时使用堆栈来跟踪它们。

另一种方法是为结构创建一个明确的公式。我们创建 7 个节点并设置它们的子节点如下:{1,2}, {3,4}, {5,6}, {7,null}, {12,34}, {56,78}, {1234,5678}。特别是如果我们以线性方案 inode ，则此模式将是:9={1,2}, 10={3,4}, 11={5,6}, 12={7,null }, 13={9,10}, 14={11,12}, 15={13,14}。简单的递增似乎给出了平衡二叉树的精确模式。这将不使用额外的内存。