Massive Algorithms: Sorted Linked List to Balanced BST

Sorted Linked List to Balanced BST | GeeksforGeeks

Same as: LeetCode 109 - Convert Sorted List to Balanced Binary Search Tree (BST)
Sorted Linked List to Balanced BST | GeeksforGeeks
Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.
we construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.
While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html
对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。

TreeNode *sortedListToBST(ListNode *&head, int start, int end)

这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.

跑一个例子：

linked list: 0->1->2->NULL

call (head(0), 0, 2)

mid = 1

node(1), head(2)

/ \

call (head(0), 0, 0) call (head(2), 2, 2)

mid = 0 mid = 2

node(0), head(1) node(2), head(NULL)

/ \ / \

call (head(0), 0, -1) call (head(0), 1, 0) call (head(2), 2, 1) call (head(0), 2, 1)

return NULL return NULL return NULL return NULL

最终结果：

/ \

0 2

http://www.programcreek.com/2013/01/leetcode-convert-sorted-list-to-binary-search-tree-java/
The order root.left=left doesn't matter.

 static ListNode h;
 public TreeNode sortedListToBST(ListNode head) {
  if (head == null)
   return null;
 
  h = head;
  int len = getLength(head);
  return sortedListToBST(0, len - 1);
 }

 // build tree bottom-up
 public TreeNode sortedListToBST(int start, int end) {
  if (start > end)
   return null;
 
  // mid
  int mid = (start + end) / 2;
 
  TreeNode left = sortedListToBST(start, mid - 1);
  TreeNode root = new TreeNode(h.val);
  h = h.next;
  TreeNode right = sortedListToBST(mid + 1, end);
 
  root.left = left;
  root.right = right;
 
  return root;
 }

struct TNode* sortedListToBST(struct LNode *head)

{

    /*Count the number of nodes in Linked List */

    int n = countLNodes(head);

    /* Construct BST */

    return sortedListToBSTRecur(&head, n);

}

struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n)

{

    /* Base Case */

    if (n <= 0)

        return NULL;

    /* Recursively construct the left subtree */

    struct TNode *left = sortedListToBSTRecur(head_ref, n/2);

    /* Allocate memory for root, and link the above constructed left 

       subtree with root */

    struct TNode *root = newNode((*head_ref)->data);

    root->left = left;

    /* Change head pointer of Linked List for parent recursive calls */

    *head_ref = (*head_ref)->next;

    /* Recursively construct the right subtree and link it with root 

      The number of nodes in right subtree  is total nodes - nodes in 

      left subtree - 1 (for root) which is n-n/2-1*/

    root->right = sortedListToBSTRecur(head_ref, n-n/2-1);

    return root;

}

From http://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);

}

http://rleetcode.blogspot.com/2014/02/convert-sorted-list-to-binary-search.html


"build tree from bottom to up, use start and end indicate the bound"


    public TreeNode sortedListToBST(ListNode head) {

if (head==null)   {


return null;


}


ListNode temp=head;




int start=0;


int end=0;


while (temp.next!=null){


temp=temp.next;


end++;


}




// java is pass by value, so inorder to memory the move of the head


// you have to put the head into a array or other warpper class


        ListNode[] headHolder={head};

return buildTree(headHolder,start, end );


}




private TreeNode buildTree(ListNode[] headHolder, int start, int end){


if (start>end){


return null;


}


int mid=(start+end)/2;




TreeNode left=buildTree(headHolder, start, mid-1);




TreeNode root=new TreeNode (headHolder[0].val);


        // current node in ListNode has been used, move it one step to the right

headHolder[0]=headHolder[0].next;




root.left=left;




TreeNode right=buildTree (headHolder, mid+1, end);


root.right=right;




return root;




}

From http://www.darrensunny.me/leetcode-convert-sorted-list-to-binary-search-tree/

public TreeNode sortedListToBST(ListNode head) {

        if (head == null)

            return null;

        // Get the number of all nodes

        int length = 0;

        for(ListNode p = head; p != null; p = p.next)

            length++;

        ArrayList<ListNode> current = new ArrayList<ListNode>();

        current.add(head);

        // Use a recursive method create the BST

        return recursiveSortedListToBST(current, length);

}

    private TreeNode recursiveSortedListToBST(ArrayList<ListNode> current, int num) {

        if (num == 0)     // Empty tree

            return null;

        if (num == 1) {   // Single-node tree

            int val = current.get(0).val;

            current.set(0, current.get(0).next);    // Update the list node to be used later

            return new TreeNode(val);

        } else {

            // Recursively construct the left subtree containing (remaining-1)/2 nodes

            TreeNode left = recursiveSortedListToBST(current, (num-1)/2);

            // Create the root based on the current list node

            TreeNode root = new TreeNode(current.get(0).val);

            root.left = left;

            // Update the list node to be used later, and recursively construct the right subtree

            current.set(0, current.get(0).next);

            root.right = recursiveSortedListToBST(current, num-1-(num-1)/2);

            return root;

}

}

Method 1
Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed.

1) Get the Middle of the linked list and make it root.
2) Recursively do same for left half and right half.
       a) Get the middle of left half and make it left child of the root
          created in step 1.
       b) Get the middle of right half and make it right child of the
          root created in step 1.

Also please refer to http://rleetcode.blogspot.com/2014/02/convert-sorted-list-to-binary-search.html


// "convert list to array first, then just convert the array to BST recursively"


    public TreeNode sortedListToBST(ListNode head) {

// Start typing your Java solution below


// DO NOT write main() function


int size=0;


ListNode temp=head;




while(temp!=null){


size++;


temp=temp.next;




}




int [] num=new int[size];


temp=head;


int i=0;




while(temp!=null){




num[i++]=temp.val;


temp=temp.next;




}




return  arrayToBST(num, 0, num.length-1);


}


    public TreeNode arrayToBST(int[] num, int start, int end){

if (start>end) return null;




int mid=(start+end)/2;




TreeNode parent=new TreeNode(num[mid]);




parent.left=arrayToBST(num, start, mid-1);


parent.right=arrayToBST(num, mid+1, end);




return parent;






}

Read full article from Sorted Linked List to Balanced BST | GeeksforGeeks

Sorted Linked List to Balanced BST | GeeksforGeeks

Labels

Popular Posts