大家好，又见面了，我是全栈君。
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
想了好久想不出来。后来看了题目分类里面说是DFS，可是没有想出DFS的算法来。后来想到了一个递归的方法。可是空间和时间都是O(n)。
后来网上找了一个空间是O(1)的时间是O(n)的算法，是一种新的解题思路，用的是中递归。
想了好久想不出来。后来看了题目分类里面说是DFS，可是没有想出DFS的算法来。后来想到了一个递归的方法。可是空间和时间都是O(n)。
后来网上找了一个空间是O(1)的时间是O(n)的算法，是一种新的解题思路，用的是中递归。
一般我解题都是用的头递归或者尾递归。第一次见识到了中递归，相当于把递归当成了一个循环体，用引用来作为变量，每一个递归中改动，须要非常强大的想象力。把整个递归树在脑子里想清楚。
空间和时间都为O(n):
TreeNode *sortedListToBST(ListNode *head)
{
vector<TreeNode*> treeNodes;
while (head != NULL)
{
TreeNode *node = new TreeNode(head->val);
treeNodes.push_back(node);
head = head->next;
}
return genBST(0, treeNodes.size()-1, treeNodes);
}
TreeNode* genBST(int start, int end, vector<TreeNode*> &treeNodes)
{
if (start == end) return treeNodes[start];
else if (start+1 == end)
{
treeNodes[start]->right = treeNodes[end];
return treeNodes[start];
}
int mid = (start+end)/2;
TreeNode* root = treeNodes[mid];
root->left = genBST(start, mid-1, treeNodes);
root->right = genBST(mid+1, end, treeNodes);
return root;
}
空间为O(1)时间为O(n)：
TreeNode *sortedListToBST(ListNode *head)
{
int len = 0;
ListNode * node = head;
while (node != NULL)
{
node = node->next;
len++;
}
return buildTree(head, 0, len-1);
}
TreeNode *buildTree(ListNode *&node, int start, int end)
{
if (start > end) return NULL;
int mid = start + (end - start)/2;
TreeNode *left = buildTree(node, start, mid-1);
TreeNode *root = new TreeNode(node->val);
root->left = left;
node = node->next;
root->right = buildTree(node, mid+1, end);
return root;
}
解法引用：http://www.bwscitech.com/a/jishuzixun/javayuyan/2013/0930/15822.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115955.html原文链接：https://javaforall.net
