Convert Sorted List to Binary Search Tree [leetcode] O(n)的算法
来源：程序员人生 发布时间：2014-10-09 07:40:56 阅读次数：3594次
主要的思想类似中序遍历，先构建左子树，再构建当前节点，并构建右子树
TreeNode *sortedListToBST(ListNode *head) {
int count = 0;
ListNode * cur = head;
while (cur)
{
count++;
cur = cur->next;
}
return sortedListToBST(head, count);
}
TreeNode *sortedListToBST(ListNode * (&head), int count) {
if (count <= 0) return NULL;
TreeNode* left = sortedListToBST(head, count / 2 );
TreeNode * root = new TreeNode(head->val);
head = head->next;
root->left = left;
root->right = sortedListToBST(head, count - (count / 2) - 1);
return root;
}
还有一个类似的题目：将二叉搜索树转换成双向链表
同样是类似中序遍历，先将左子树变成双向链表，再处理右子树
代码如下：
void BSTToList(TreeNode * t, ListNode * &l)
{
if (t->left) BSTToList(t->left, l);
ListNode * cur = new ListNode(t->val);
cur->left = l;
if (!l) l->right = cur;
l = cur;
if (t->right) BSTToList(t->right, l);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
