5

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

[编辑]

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

[编辑2]

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

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
}
4

2 回答 2

0

提前假设您希望它是这样的，大致如下：

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

然后你可以明确地解决结构。在这种情况下，对于某个整数 N 的长度 L<2 N的列表，并假设您创建所有节点并将一些叶子保留为“null”（或者甚至不构造这些节点），您有树中的节点等于 (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}：特别是如果我们以线性方案索引节点，则此模式将是：9={1,2}, 10={3,4}, 11={5,6}, 12={7,null}, 13={9,10}, 14={11,12}, 15={13,14}. 简单地递增似乎给出了平衡二叉树的确切模式。这不会使用额外的内存。

于 2012-08-29T08:01:19.700 回答
-1

您可以通过模拟堆栈将任何递归解决方案转换为“迭代”解决方案。

于 2012-08-29T05:38:19.720 回答