Convert Sorted List to Binary Search Tree
今天是一道有關(guān)鏈表和二叉樹(shù)的題目颊郎，來(lái)自LeetCode但金，難度為Medium，Acceptance為26%遣臼。
題目如下
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Example：
Example
解題思路及代碼見(jiàn)閱讀原文
回復(fù)0000查看更多題目
解題思路
首先翘单，該題還是有難度的，但是我們換一個(gè)思路可能就會(huì)簡(jiǎn)單很多伪冰，即如果是將一個(gè)排序二叉樹(shù)轉(zhuǎn)換成鏈表誓酒，相信大多數(shù)同學(xué)都會(huì)做，無(wú)非是一個(gè)中序遍歷。
那么靠柑，這里講鏈表轉(zhuǎn)換成二叉樹(shù)也是一樣的思路寨辩，即一個(gè)中序遍歷，其具體思路如下歼冰。
按照中序遍歷的思路靡狞，應(yīng)該先生成左子樹(shù)，然后是根節(jié)點(diǎn)隔嫡，最后的右子樹(shù)甸怕。那么，很明顯這是一個(gè)遞歸的結(jié)構(gòu)腮恩。那么剩下的問(wèn)題就是如何確定遞歸的終止條件梢杭。
因?yàn)樵谵D(zhuǎn)換的過(guò)程中，需要計(jì)算各子鏈表的長(zhǎng)度秸滴，那么這里就可以由此來(lái)終止遞歸武契，即當(dāng)長(zhǎng)度等于0時(shí)終止。下面我們來(lái)看代碼缸榛。
代碼如下
C++版
class Solution {
public:
ListNode *list;
int count(ListNode *node){
int size = 0;
while (node) {
++size;
node = node->next;
}
return size;
}
TreeNode *generate(int n){
if (n == 0)
return NULL;
TreeNode *node = new TreeNode(0);
node->left = generate(n / 2);
node->val = list->val;
list = list->next;
node->right = generate(n - n / 2 - 1);
return node;
}
TreeNode *sortedListToBST(ListNode *head) {
this->list = head;
return generate(count(head));
}
};
java版
private ListNode node;
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
int size = 0;
ListNode runner = head;
node = head;
while(runner != null){
runner = runner.next;
size ++;
}
return inorderHelper(0, size - 1);
}
public TreeNode inorderHelper(int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start) / 2;
TreeNode left = inorderHelper(start, mid - 1);
TreeNode treenode = new TreeNode(node.val);
treenode.left = left;
node = node.next;
TreeNode right = inorderHelper(mid + 1, end);
treenode.right = right;
return treenode;
}
關(guān)注我
該公眾號(hào)會(huì)每天推送常見(jiàn)面試題吝羞，包括解題思路是代碼，希望對(duì)找工作的同學(xué)有所幫助
image
