Convert Sorted List to Binary Search Tree [leetcode] O(n)的算法
來源：程序員人生 發(fā)布時(shí)間：2014-10-09 07:40:56 閱讀次數(shù)：3851次
主要的思想類似中序遍歷，先構(gòu)建左子樹，再構(gòu)建當(dāng)前節(jié)點(diǎn)，并構(gòu)建右子樹
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;
}
還有一個(gè)類似的題目：將二叉搜索樹轉(zhuǎn)換成雙向鏈表
同樣是類似中序遍歷，先將左子樹變成雙向鏈表，再處理右子樹
代碼如下：
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);
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
