Convert Sorted List to Binary Search Tree · 數據結構與算法/leetcode/lintcode題解

# Convert Sorted List to Binary Search Tree ### Source - leetcode - [Convert Sorted List to Binary Search Tree | LeetCode OJ](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/) - lintcode - [(106) Convert Sorted List to Binary Search Tree](http://www.lintcode.com/en/problem/convert-sorted-list-to-binary-search-tree/) ~~~ Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. ~~~ ### 題解 - 折半取中題 [Convert Sorted Array to Binary Search Tree | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/binary_search_tree/convert_sorted_array_to_binary_search_tree.html) 的升級版，不過這里把「有序數組」換成了「有序鏈表」。我們可以參考上題的題解思路，思考如何才能在鏈表中找到「中間節點」。對于本題的單向鏈表來說，要想知道中間位置的節點，則必須需要知道鏈表的長度，因此我們就自然聯想到了可以通過遍歷鏈表來求得其長度。求得長度我們就知道了鏈表中間位置節點的索引了，進而根據頭節點和當前節點則可將鏈表分為左右兩半形成遞歸模型。到這里還只能算是解決了問題的一半，這道題另一比較麻煩的地方在于邊界條件的取舍，很難第一次就 AC, 下面結合代碼做進一步的分析。 ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: a tree node */ TreeNode *sortedListToBST(ListNode *head) { if (NULL == head) { return NULL; } // get the size of List ListNode *node = head; int len = 0; while (NULL != node) { node = node->next; ++len; } return buildBSTHelper(head, len); } private: TreeNode *buildBSTHelper(ListNode *head, int length) { if (NULL == head || length <= 0) { return NULL; } // get the middle ListNode as root TreeNode ListNode *lnode = head; int count = 0; while (count < length / 2) { lnode = lnode->next; ++count; } TreeNode *root = new TreeNode(lnode->val); root->left = buildBSTHelper(head, length / 2); root->right = buildBSTHelper(lnode->next, length - 1 - length / 2); return root; } }; ~~~ ### 源碼分析 1. 異常處理。 1. 獲取鏈表長度。 1. `buildBSTHelper`輸入參數為表頭節點地址以及相應的鏈表長度，遞歸獲取根節點、左節點和右節點。其中`buildBSTHelper`的邊界處理很有技巧，首先是遞推的終止條件，頭節點為`NULL`時顯然應該返回`NULL`. 但`length`的終止條件又如何確定？拿不定主意時就用幾個簡單例子來試試，比如`1`, `1->2`, `1->2->3`. 先來分析下給`buildBSTHelper`傳入的`length`的含義——從表頭節點`head`開始往后遞推長度為`length`的鏈表。故`length`為0時表示不訪問鏈表中的任一節點，也就是說應該返回`NULL`. 再來分析鏈表的中間位置如何確定，我們引入計數器`count`來表示**目前需要遍歷`count`個鏈表節點數目**才能得到中間位置的節點。看看四種不同鏈表長度下的表現。 1. 鏈表長度為1時，中間位置即為自身，計數器的值為0. 1. 鏈表長度為2時，中間位置可選第一個節點，也可選第二個節點，相應的計數器值為0或1. 1. 鏈表長度為3時，中間位置為第二個節點，相應的計數器應為1，表示從表頭節點往后遞推一個節點。 1. 鏈表長度為4時，... 計數器的值為1或者2. 從以上四種情況我們可以推斷出`count`的值可取為`length / 2`或者`length / 2 + 1`, 簡單起見我們先取`length / 2`試試，對應的邊界條件即為`count < length / 2`, `count`初始值為0. 經過`count`次迭代后，目前`lnode`即為所需的鏈表中間節點，取出其值初始化為`TreeNode`的根節點。確定根節點后還需要做的事情就是左子樹和右子樹中鏈表頭和鏈表長度的取舍。首先來看看左子樹根節點的確定，**`count`的含義為到達中間節點前遍歷過的鏈表節點數目，那么從另一方面來說它就是前半部分鏈表的長度！**故將此長度`length / 2`作為得到左子樹根節點所需的鏈表長度參數。除掉鏈表前半部分節點和中間位置節點這兩部分外，剩下的鏈表長度即為`length - 1 - length / 2`. ****> `length - 1 - length / 2 != length / 2 - 1` 有沒有覺得可以進一步化簡為`length / 2 - 1`? 我首先也是這么做的，后來發現一直遇到`TERMSIG= 11`錯誤信息，這種錯誤一般是指針亂指或者指針未初始化就去訪問。但自己仔細檢查后發現并沒有這種錯誤，于是乎在本地做單元測試，發現原來是死循環造成了棧空間溢出(猜的)！也就是說邊界條件有問題！可自己的分析明明是沒啥問題的啊... 在這種情況下我默默地打開了九章的參考代碼，發現他們竟然沒有用`length / 2 - 1`，而是`length - 1 - length / 2`. 立馬意識到這兩者可能并不相等。用錯誤數據試了下，長度為1或者3時兩者即不相等。知道對于整型數來說，`1 / 2`為0，但是卻沒能活學活用，血淚的教訓。:-( 一個美好的下午就沒了。在測試出錯的時候，還是要相信測試數據的力量，而不是憑自己以前認為對的方式去解決問題。 ### 復雜度分析首先遍歷鏈表得到鏈表長度，復雜度為 O(n)O(n)O(n). 遞歸遍歷鏈表時，每個鏈表節點被訪問一次，故時間復雜度為 O(n)O(n)O(n), 兩者加起來總的時間復雜度仍為 O(n)O(n)O(n). ### 進一步簡化代碼 ~~~ class Solution { public: TreeNode *sortedListToBST(ListNode *head) { int length = 0; ListNode *curr = head; while (curr != NULL) { curr = curr->next; ++length; } return helper(head, length); } private: TreeNode *helper(ListNode *&pos, int length) { if (length <= 0) { return NULL; } TreeNode *left = helper(pos, length / 2); TreeNode *root = new TreeNode(pos->val); // the sequence cannot be changed! // this is important difference of the solution above pos = pos->next; root->left = left; root->right = helper(pos, length - length / 2 - 1); return root; } }; ~~~ ### 源碼分析 1. 可以進一步簡化 helper 函數代碼，注意參數的接口設計。 1. 即是把傳入的鏈表指針向前遞進 n 步，并返回經過的鏈表節點轉化成的二分查找樹的根節點。 1. 注意注釋中的那兩句實現，`new root` 和 `new left` 不可調換順序。這才是精簡的要點。但是這種方法不如上面的分治法容易理解。 ### O(nlogn) 的實現，避免 length 邊界 ~~~ /** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param head: The first node of linked list. * @return: a tree node */ public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } return helper(head); } private TreeNode helper(ListNode head) { if (head == null) { return null; } if (head.next == null) { return new TreeNode(head.val); } ListNode pre = null; ListNode slow = head, fast = head; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; TreeNode root = new TreeNode(slow.val); TreeNode L = helper(head); TreeNode R = helper(slow.next); root.left = L; root.right = R; return root; } } ~~~ ### 源碼分析 1. 如果想避免上述 length 邊界搞錯的問題，可以使用分治法遍歷樹求中點的方法。 1. 但這種時間復雜度是 O(nlogn)O(nlogn)O(nlogn)，性能上還是比 O(n)O(n)O(n) 差一點。 ### Reference - [Convert Sorted List to Binary Search Tree | 九章算法](http://www.jiuzhang.com/solutions/convert-sorted-list-to-binary-search-tree/)