Convert Sorted List to Binary Search Tree [leetcode] O(n)的算法
來源：程序員人生 發布時間：2014-10-09 07:40:56 閱讀次數：3858次
主要的思想類似中序遍歷，先構建左子樹，再構建當前節點，并構建右子樹
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);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
