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

Question

从排序的单链表创建平衡二叉搜索树的最佳方法是什么？

Answer 1

自下而上创建节点怎么样？

该解法的时间复杂度为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);
}

Answer 2

你不能比线性时间做得更好，因为你至少必须读取列表的所有元素，所以你不妨将列表复制到数组中（线性时间），然后以通常的方式有效地构造树，即，如果您有列表 [9,12,18,23,24,51,84]，那么您首先将 23 设为根，子级为 12 和 51，然后 9 和 18 成为 12 和 24 的子级84 成为 51 的孩子。总的来说，如果你做对了，应该是 O(n) 。

实际的算法是“以列表的中间元素作为根，并递归地为中间元素左侧和右侧的子列表构建 BST，并将它们附加到根下方”。

Answer 3

最佳不仅仅与无症状运行时间有关。排序链表具有直接创建二叉树所需的所有信息，我认为这可能就是他们正在寻找的内容。

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

在伪代码中

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 的答案更好，除非我能想出一种在树构建时重新平衡树的方法。

Answer 4

诡计问题！

最好的方法是使用 STL，并利用排序关联容器 ADT（其中 set 是一个实现）的事实，要求插入已分摊线性时间的排序范围。任何语言的任何可通过的核心数据结构集都应该提供类似的保证。要获得真正的答案，请参阅其他人提供的相当聪明的解决方案。

---

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

嗯...

这个怎么样？

平衡二叉树中最小的可能有意义的树是 3 个节点。
一位家长，还有两个孩子。这种树的第一个实例是前三个元素。孩子-父母-孩子。现在让我们将其想象为单个节点。好吧，我们不再有一棵树了。但我们知道我们想要的形状是Child-parent-Child。
暂时完成我们的想象，我们希望在最初的三巨头中保留一个指向父级的指针。但它是单向链接的！
我们需要四个指针，我将其称为 A、B、C 和 D。因此，我们将 A 移至 1，将 B 设置为 A 并将其前移 1。设 C 等于 B，并将其前进 2。 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下的Node的指针指向B下的节点。
从任何意义上来说，这都是作弊，但通过使用这个技巧，我们释放了 B。
或者，您可以保持理智，并实际开始构建节点结构。毕竟，您确实无法重用 SLL 中的节点，它们可能是 POD 结构。

现在...

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

并且...等一下。如果我们让自己将 C 视为单个节点而不是树，我们可以使用相同的技巧来释放 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 次。问题在于，这依赖于给出一个列表，该列表将形成真正平衡的二叉搜索树。换句话说，存在一些隐藏的约束，可能会使该解决方案更难以应用或不可能。例如，如果您有奇数个元素，或者有很多非唯一值，这就会开始生成一棵相当愚蠢的树。

注意事项：

• 使元素独一无二。
• 如果节点数为奇数，则在末尾插入一个虚拟元素。
• 渴望有一个更天真的实现。
• 使用双端队列来保留已完成的子树的根和中点，而不是乱搞我的第二个技巧。

Answer 5

这是一个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

Answer 6

我被要求在一个排序数组上创建一个最小高度的 BST，而不是排序的链表（虽然逻辑上无关紧要，但运行时会有所不同），以下是我可以获得的代码：

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); 

HTH Somebody..

Answer 7

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

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 will now be at the middle element. 
   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); 
}

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

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

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

Answer 8

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

在@Stuart 的回答中，他提供的数组是 BST 的支持数据结构。例如，查找操作只需要执行索引数组计算即可遍历树。增长数组和删除元素将是更棘手的部分，因此我更喜欢向量或其他恒定时间查找数据结构。

@Jake的答案也使用了这个事实，但不幸的是需要您遍历列表来查找每次执行 get(index) 操作。但不需要额外的内存使用。

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

在这样的问题中，如果你讨论了权衡和所有的选择，你会得到额外的分数。

Answer 9

希望这篇文章的详细解释对您有所帮助：
http://preparefortechinterview.blogspot.com/2013/10/planting-trees_1.html

Answer 10

来自 @1337c0d3r 我的博客中的实现略有改进< /a>.

// create a balanced BST using @len elements starting from @head & move @head forward by @len
TreeNode *sortedListToBSTHelper(ListNode *&head, int len) {
    if (0 == len)   return NULL;

    auto left = sortedListToBSTHelper(head, len / 2);
    auto root = new TreeNode(head->val);
    root->left = left;
    head = head->next;
    root->right = sortedListToBSTHelper(head, (len - 1) / 2);
    return root;
}

TreeNode *sortedListToBST(ListNode *head) {
    int n = length(head);
    return sortedListToBSTHelper(head, n);
}

Answer 11

如果您知道链表中有多少个节点，您可以这样做：

// 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 。它实际上更通用，是使用任何前向迭代器而不是专门的链表的模板。