logo标签列表

从已排序的链表创建平衡二叉搜索树

algorithmtreelinked-list
21

如何从已排序的单链表创建一个平衡的二叉搜索树？

2
几个问题: 你知道sll中元素的数量吗？ - Jake Kurzer
11个回答
28
如何从底部向上创建节点？
这个解决方案的时间复杂度为O(N)。详细的解释可以查看我在博客中的文章： http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html 我们只需要对链表进行两次遍历。第一次遍历获取链表长度（然后将其作为参数n传递给函数），然后按照列表的顺序创建节点。
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);
}
1
我非常喜欢这种自下而上的方法，它确实是O（N）。 - Timothy Chen
1
为什么我们需要执行list = list->next;？ - user1772643
博客文章显示页面未找到。请问您能否帮忙更新链接？ - Kosy Anyanwu
4
你不能做得比线性时间更好，因为你至少要读取列表的所有元素，所以最好将列表复制到数组中（线性时间），然后按照通常的方式高效地构建树，即如果你有列表[9,12,18,23,24,51,84]，那么你会从23开始，使其成为根节点，子节点为12和51，然后9和18成为12的子节点，24和84成为51的子节点。如果正确执行，整体应该是O(n)。
实际算法是，“以列表的中间元素作为根节点，并递归地构建左侧和右侧子列表的BST，并将它们连接到根节点下方”。
你应该能够在遍历链表时构建树，而无需先将其复制到数组中... - The Archetypal Paul
我们两种算法的区别非常有趣（至少对我来说是这样）。你是自上而下构建树，而我是自下而上构建。 - The Archetypal Paul
我也觉得很有趣 :) 只是看了一下 -- 我曾经走开去做一些工作... - Stuart Golodetz
我们都使用了栈。你的栈隐含在调用栈中，而我的是显式的。 - The Archetypal Paul
1
我认为它也是这样做的。唯一不同的是，我没有将整个链表转换为int，而是创建了一个树节点数组。然后使用递归将树节点链接在一起，这样我们就不会浪费内存。 - Timothy Chen
2

巧妙的问题！

最好的方法是使用STL，并利用排序的关联容器ADT，其中集合是一种实现，要求插入排序范围具有摊销线性时间。 任何语言的可接受核心数据结构集都应该提供类似的保证。对于真正的答案，请查看其他人提供的相当聪明的解决方案。

那是什么？我应该提供一些有用的东西吗？

嗯……

这个怎么样？

在平衡二叉树中，最小的有意义的树是3个节点。一个父节点和两个子节点。这样的树的第一个实例是前三个元素。子节点-父节点-子节点。现在让我们把它想象成一个单一的节点。好吧，我们不再有一棵树了。但我们知道我们想要的形状是子节点-父节点-子节点。
暂时完成我们的想象，我们想保留指向那个初始三人组父节点的指针。但它是单向链接的！
我们将需要四个指针，我将其称为A、B、C和D。所以，我们将A移到1，将B设置为A并向前移动一个。将C设置为B，并向前移动两个。节点下方的B已经指向其即将成为右子节点的节点。我们构建了我们的初始树。我们将B留在第一棵树的父节点处。C坐在将拥有我们的两棵最小树作为子节点的节点上。将A设置为C，并向前移动一个。将D设置为A，并向前移动一个。现在我们可以构建我们的下一个最小树。D指向该树的根，B指向另一个树的根，而C指向…将挂我们的两棵最小树的新根。

要些图片吗？

[A][B][-][C]

以我们的最小树形图为节点的形象...

[B = Tree][C][A][D][-]

然后

[Tree A][C][Tree B]

除此之外，我们还有一个问题。在D之后的第二个节点是我们的下一个根节点。
[B = Tree A][C][A][D][-][Roooooot?!]

如果我们只能维护指向C的指针而不是指向它和C的指针，那将会更容易。事实证明，由于我们知道它将指向C，因此我们可以开始构建二叉树中将保存它的节点，并将C作为其左节点输入。如何优雅地实现这一点呢？

将C下面的节点指针设置为B下面的节点。
在某种程度上，这是作弊，但通过使用这个技巧，我们可以释放B。
或者，你也可以理智地开始构建节点结构。毕竟，你不能重用SLL中的节点，它们可能是POD结构。

现在...

[TreeA]<-[C][A][D][-][B]  
[TreeA]<-[C]->[TreeB][B]

等一下...我们可以使用相同的技巧来释放C，只需将其视为单个节点而不是树即可。毕竟，它确实只是一个单独的节点。

[TreeC]<-[B][A][D][-][C]

我们可以进一步概括我们的技巧。
[TreeC]<-[B][TreeD]<-[C][-]<-[D][-][A]    
[TreeC]<-[B][TreeD]<-[C]->[TreeE][A]  
[TreeC]<-[B]->[TreeF][A]  
[TreeG]<-[A][B][C][-][D]
[TreeG]<-[A][-]<-[C][-][D]  
[TreeG]<-[A][TreeH]<-[D][B][C][-]  
[TreeG]<-[A][TreeH]<-[D][-]<-[C][-][B]  
[TreeG]<-[A][TreeJ]<-[B][-]<-[C][-][D]  
[TreeG]<-[A][TreeJ]<-[B][TreeK]<-[D][-]<-[C][-]      
[TreeG]<-[A][TreeJ]<-[B][TreeK]<-[D][-]<-[C][-]

我们缺少一个关键步骤！
[TreeG]<-[A]->([TreeJ]<-[B]->([TreeK]<-[D][-]<-[C][-]))

变成：

[TreeG]<-[A]->[TreeL->([TreeK]<-[D][-]<-[C][-])][B]    
[TreeG]<-[A]->[TreeL->([TreeK]<-[D]->[TreeM])][B]  
[TreeG]<-[A]->[TreeL->[TreeN]][B]  
[TreeG]<-[A]->[TreeO][B]  
[TreeP]<-[B]

显然，算法可以大大简化，但我认为演示如何通过迭代设计算法来进行优化是很有趣的。我认为这种过程比任何其他东西都更能吸引一个好的雇主。
基本上，诀窍在于每次到达下一个中点时，我们知道它是一个即将成为父节点的节点，并且我们知道它的左子树已经完成。另一个诀窍是，一旦一个节点有两个孩子和指向它的东西，即使所有子树还没有完成，我们也完成了该节点。使用这个方法，我们可以得到我相信是一个线性时间解决方案，因为每个元素最多只被触摸4次。问题是这依赖于给定一个将形成真正平衡的二叉搜索树的列表。换句话说，有一些隐藏的限制可能会使这个解决方案变得更难应用，或者不可能。例如，如果你有奇数个元素，或者有很多非唯一值，这开始产生一个相当愚蠢的树。
考虑以下几点：
- 使元素唯一。 - 如果节点数是奇数，在最后插入一个虚拟元素。 - 渴望使用更加天真的实现。 - 使用双端队列来保存已完成子树和中点的根，而不是使用我的第二个诀窍。
我觉得我错过了什么，我很匆忙，没有进行正式的证明。有人看到错误了吗？我觉得破解一个RB树实现可能更容易些。 - Jake Kurzer
我理解向雇主清晰地展示你的想法的重要性。然而，在面试时，我只有25分钟的时间，从听取电话上的问题到在屏幕上输入工作解决方案代码。因此，我认为这么多的文字无法及时完成它。 - Timothy Chen
2

最好不仅仅是关于渐进运行时间的。排序的链表具有直接创建二叉树所需的所有信息，我认为这可能是他们正在寻找的。

请注意，第一个和第三个条目成为第二个条目的子级，然后第四个节点具有第二个和第六个节点的子级（其子级为第五个和第七个），依此类推...

伪代码如下：

read three elements, make a node from them, mark as level 1, push on stack
loop
    read three elemeents and make a node of them
    mark as level 1
    push on stack
    loop while top two enties on stack have same level (n)
         make node of top two entries, mark as level n + 1, push on stack
while elements remain in list

（在剩余不到三个元素或出现不平衡树的情况下进行一些调整）。
编辑：
在任何时候，堆栈中有一个高度为N的左节点。下一步是读取一个元素，然后读取并构造另一个高度为N的节点。要构造高度为N的节点，请在堆栈上制作并推送高度为N-1的节点，然后读取一个元素，在堆栈上制作另一个高度为N-1的节点——这是一个递归调用。
实际上，这意味着该算法（即使经过修改）也不会产生平衡树。如果有2N+1个节点，则会产生一个左侧具有2N-1个值且右侧只有1个值的树。
因此，我认为@sgolodetz的答案更好，除非我能想到一种在构建树时重新平衡树的方法。
从伪代码中我不清楚你的算法具体在做什么--当你说“标记为等级1”时，你是只将这三个元素中间的一个标记为等级1，还是将它们全部标记为等级1？你能澄清一下吗？ - Stuart Golodetz
2
当您将节点设置为前两个条目时，具体细节是什么？ - Timothy Chen
@Paul：和Timothy一样的问题 :) 所以你有两个包含[9,12,18]和[23,24,51]的节点，你将它们组合起来得到了什么...？ - Stuart Golodetz
是的，有一个缺陷。你需要有一个节点[9, 12, 18]，值为23，和一个节点[24, 51, 84]。不过可以修复。 - The Archetypal Paul
我认为可以通过始终读取一个更多的元素并将其推入来修复它。 - The Archetypal Paul
显示剩余3条评论
2
这是一个Python的实现：
def sll_to_bbst(sll, start, end):
    """Build a balanced binary search tree from sorted linked list.

    This assumes that you have a class BinarySearchTree, with properties
    'l_child' and 'r_child'.

    Params:
        sll: sorted linked list, any data structure with 'popleft()' method,
            which removes and returns the leftmost element of the list. The
            easiest thing to do is to use 'collections.deque' for the sorted
            list.
        start: int, start index, on initial call set to 0
        end: int, on initial call should be set to len(sll)

    Returns:
        A balanced instance of BinarySearchTree

    This is a python implementation of solution found here: 
    http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

    """

    if start >= end:
        return None

    middle = (start + end) // 2
    l_child = sll_to_bbst(sll, start, middle)
    root = BinarySearchTree(sll.popleft())
    root.l_child = l_child
    root.r_child = sll_to_bbst(sll, middle+1, end)

    return root
1

我被要求在一个有序数组上创建最小高度的二叉搜索树，而不是排序的链表（逻辑上并没有关系，但运行时间确实会有所不同）。以下是我能够得到的代码：

typedef struct Node{
     struct Node *left;
     int info;
     struct Node  *right;
}Node_t;

Node_t* Bin(int low, int high) {

     Node_t* node = NULL;
     int mid = 0;

     if(low <= high) {
         mid = (low+high)/2;
         node = CreateNode(a[mid]);
         printf("DEBUG: creating node for %d\n", a[mid]);

        if(node->left == NULL) {
            node->left = Bin(low, mid-1);
        }

        if(node->right == NULL) {
            node->right = Bin(mid+1, high);
        }

        return node;
    }//if(low <=high)
    else {
        return NULL;
    }
}//Bin(low,high)


Node_t* CreateNode(int info) {

    Node_t* node = malloc(sizeof(Node_t));
    memset(node, 0, sizeof(Node_t));
    node->info = info;
    node->left = NULL;
    node->right = NULL;

    return node;

}//CreateNode(info)

// call function for an array example: 6 7 8 9 10 11 12, it gets you desired 
// result

 Bin(0,6);

希望对某人有所帮助。

0
如果您知道链表中有多少个节点，可以这样做：
// Gives path to subtree being built.  If branch[N] is false, branch
// less from the node at depth N, if true branch greater.
bool branch[max depth];

// If rem[N] is true, then for the current subtree at depth N, it's
// greater subtree has one more node than it's less subtree.
bool rem[max depth];

// Depth of root node of current subtree.
unsigned depth = 0;

// Number of nodes in current subtree.
unsigned num_sub = Number of nodes in linked list;

// The algorithm relies on a stack of nodes whose less subtree has
// been built, but whose right subtree has not yet been built.  The
// stack is implemented as linked list.  The nodes are linked
// together by having the "greater" handle of a node set to the
// next node in the list.  "less_parent" is the handle of the first
// node in the list.
Node *less_parent = nullptr;

// h is root of current subtree, child is one of its children.
Node *h, *child;

Node *p = head of the sorted linked list of nodes;

LOOP // loop unconditionally

    LOOP WHILE (num_sub > 2)
        // Subtract one for root of subtree.
        num_sub = num_sub - 1;

        rem[depth] = !!(num_sub & 1); // true if num_sub is an odd number
        branch[depth] = false;
        depth = depth + 1;
        num_sub = num_sub / 2;
    END LOOP

    IF (num_sub == 2)
        // Build a subtree with two nodes, slanting to greater.
        // I arbitrarily chose to always have the extra node in the
        // greater subtree when there is an odd number of nodes to
        // split between the two subtrees.

        h = p;
        p = the node after p in the linked list;
        child = p;
        p = the node after p in the linked list;
        make h and p into a two-element AVL tree;
    ELSE  // num_sub == 1

        // Build a subtree with one node.

        h = p;
        p = the next node in the linked list;
        make h into a leaf node;
    END IF

    LOOP WHILE (depth > 0)
        depth = depth - 1;
        IF (not branch[depth])
            // We've completed a less subtree, exit while loop.
            EXIT LOOP;
        END IF

        // We've completed a greater subtree, so attach it to
        // its parent (that is less than it).  We pop the parent
        // off the stack of less parents.
        child = h;
        h = less_parent;
        less_parent = h->greater_child;
        h->greater_child = child;
        num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1;
        IF (num_sub & (num_sub - 1))
          // num_sub is not a power of 2
          h->balance_factor = 0;
        ELSE
          // num_sub is a power of 2
          h->balance_factor = 1;
        END IF
    END LOOP

    IF (num_sub == number of node in original linked list)
        // We've completed the full tree, exit outer unconditional loop
        EXIT LOOP;
    END IF

    // The subtree we've completed is the less subtree of the
    // next node in the sequence.

    child = h;
    h = p;
    p = the next node in the linked list;
    h->less_child = child;

    // Put h onto the stack of less parents.
    h->greater_child = less_parent;
    less_parent = h;

    // Proceed to creating greater than subtree of h.
    branch[depth] = true;
    num_sub = num_sub + rem[depth];
    depth = depth + 1;

END LOOP

// h now points to the root of the completed AVL tree.

关于C++的编码，请参见https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.h中的build成员函数（当前位于第361行）。实际上，它更通用，使用任何前向迭代器的模板，而不是特定的链表。

0

这是我建议的伪递归算法。


createTree(treenode *root, linknode *start, linknode *end)
{
   if(start == end or start = end->next)
   {
      return; 
   } 
   ptrsingle=start;
   ptrdouble=start;
   while(ptrdouble != end and ptrdouble->next !=end)
   {
    ptrsignle=ptrsingle->next;
    ptrdouble=ptrdouble->next->next;
   }
   //ptrsignle现在将位于中间元素。 
   treenode cur_node=Allocatememory;
   cur_node->data = ptrsingle->data;
   if(root = null)
       {
           root = cur_node; 
       }
   else
      {
         if(cur_node->data (less than) root->data)
          root->left=cur_node
         else
           root->right=cur_node
      }
   createTree(cur_node, start, ptrSingle);
   createTree(cur_node, ptrSingle, End); 
}

Root = null; 初始调用将是createtree(Root, list, null);

我们正在进行树的递归构建，但不使用中间数组。为了每次到达中间元素，我们将推进两个指针，一个按一个元素，另一个按两个元素。当第二个指针到达末尾时，第一个指针将在中间。

运行时间将为o(nlogn)。额外空间将为o(logn)。对于实际情况下可能有保证nlogn插入的R-B树来说，这不是一种有效的解决方案。但对于面试来说已经足够好了。

0

与@Stuart Golodetz和@Jake Kurzer类似，重要的是列表已经排序。

在@Stuart的答案中，他提供的数组是BST的支撑数据结构。例如，查找操作只需要执行索引数组计算以遍历树。增加数组大小和删除元素将是更棘手的部分，因此我更喜欢使用向量或其他具有常数时间查找数据结构。

@Jake的答案也利用了这一事实，但不幸的是需要遍历列表以每次执行get（index）操作。但不需要额外的内存使用。

除非面试官特别提到他们想要树的对象结构表示，否则我会使用@Stuart的答案。

在这样的问题中，您将获得额外的分数，因为您讨论了权衡和所有可用选项。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接