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节点。
The order root.left=left doesn't matter.
From http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
http://rleetcode.blogspot.com/2014/02/convert-sorted-list-to-binary-search.html
Read full article from Sorted Linked List to Balanced BST | GeeksforGeeks
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
最终结果：
1
/ \
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;}
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
From http://www.darrensunny.me/leetcode-convert-sorted-list-to-binary-search-tree/"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 classListNode[] 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 rightheadHolder[0]=headHolder[0].next;root.left=left;TreeNode right=buildTree (headHolder, mid+1, end);root.right=right;return root;}
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.
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() functionint 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
