每天一道leetcode109-有序鏈表轉換為二叉搜索樹

109_(有序鏈表轉換為二叉搜索樹)Convert Sorted List to Binary Search Tree

1 問題描述、輸入輸出與樣例

1.1 問題描述

給定一個單鏈表，其中的元素按升序排序，將其轉換為高度平衡的二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。

1.2 輸入與輸出

輸入：

• ListNode* head：有序鏈表的頭節點指針
  
  輸出：
  

• output_type:TreeNode*：高度平衡二叉搜索樹的根節點指針

1.3 樣例

1.3.1 樣例1

輸入:

給定的有序鏈表： [-10, -3, 0, 5, 9]

輸出:

一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：

 0
 / \
 -3 9
 / /
 -10 5

2 思路描述與代碼

2.1 思路描述（快慢指針+遞歸）

1. 快慢指針分離成左子樹所有節點構成的鏈表、根節點和右子樹所有節點構成的鏈表

2. 根據根節點遞歸分離的兩個鏈表，第一個鏈表為左子樹，第二個鏈表為右子樹

比如給定的有序鏈表： [-10, -3, 0, 5, 9]

先分離鏈表為list1 = [-10, -3], 根節點root的值 0, list2 = [5, 9];

遞歸左子樹root->left = sortedListToBST(list1), root->right = sortedListToBST(list2)

根據同樣的方法可以獲取 root 左右二叉搜索子樹分別是:

 -3 9
 / /
 -10 5

於是構造出的二叉搜索樹是:

 0
 / \
 -3 9
 / /
 -10 5

2.2 代碼

 
//函數中涉及到的指針操作
//head 為 ListNode* 類型的指針， head->val 是這個指針所指向的節點的值
//head->next 為 head 所指向的節點的下一個節點的指針

//TreeNode* root = new TreeNode(val) 返回從堆中生成一個值為 val 的鏈表節點的指針給root
//root->left 是 root 所指向節點的左子樹根節點的指針, root->right 同理

//解題思路
//1.快慢指針分離成左子樹所有節點構成的鏈表、根節點和右子樹所有節點構成的鏈表
//2.根據根節點遞歸分離的兩個鏈表，第一個鏈表為左子樹，第二個鏈表為右子樹 
TreeNode* sortedListToBST(ListNode* head) {
 //邊界情況:鏈表為空或者只有一個節點
 if 
(head == nullptr) return nullptr;
 if(head->next == nullptr) return new TreeNode(head->val);

 //1.快慢指針分離成根節點、左子樹所有節點構成的鏈表和右子樹所有節點構成的鏈表
 //slow為二叉搜索樹左子樹所有節點構成的鏈表的鏈表的尾巴，其鏈表頭為head
 //slow->next->val為二叉搜索樹根節點的值
 //slow->next->next為二叉搜索樹右子樹所有節點構成的鏈表的頭節點指針
 ListNode *slow = head, *fast = head->next;
 while( fast != nullptr ){
 fast = fast->next == nullptr ? nullptr : fast->next->next;
 slow = fast == nullptr ? slow : slow->next;
 }
 //2. 根據根節點遞歸分離的兩個鏈表，第一個鏈表為左子樹，第二個鏈表為右子樹
 TreeNode* root = new TreeNode(slow->next->val);
 slow->next = nullptr; 
//分離第一個鏈表
 ListNode* list2head = slow->next->next;//獲取第二個鏈表的頭節點指針
 //遞歸構造二叉搜索樹
 root->left = sortedListToBST(head);
 root->right = sortedListToBST(list2head);
 return root;
}

3 思考與拓展

3.1 思考

本題數據是基於鏈表的結構，獲取中間值相比於數組是要花很大的代價的，所以時間複雜度變大了。

3.1.1 其他方法

無。

3.1.2 複雜度分析

3.1.3 難點分析

1. 快慢指針分離鏈表

2. 邊界情況的考慮

3.2 拓展

如果給定的鏈表不是有序的呢？會影響他的時間複雜度嗎？

閱讀更多 程序員喬戈裡 的文章

關鍵字: 二叉 樣例 計算複雜性理論