[LeetCode] 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.

思路：
非常巧妙的题目，解答时参考了这篇文章： http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

这题和Convert Sorted Array to Binary Search Tree那题看上去很像，但是从array变成了linked list，就不能O(1)寻找中间节点了。一种直接的修改就是每次遍历一半的节点来找寻中间节点。如何在不知道linked list总长的情况下遍历一半节点？双指针策略，快指针一次走2个节点，慢指针一次走1个节点，当快指针到尾部时，慢指针对应的即为中间节点。但这种方法的时间复杂度为O(N logN)：每层递归一共访问N/2个节点，一共log N层递归（对应树的高度）。

对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: TreeNode *sortedListToBST(ListNode *head) { int listLen = 0; ListNode *cur = head; while(cur) { listLen++; cur = cur->next; } return sortedListToBST(head, 0, listLen-1); } TreeNode *sortedListToBST(ListNode *&head, int start, int end) { if(start>end) return NULL; int mid = start + (end-start)/2; TreeNode *leftChild = sortedListToBST(head, start, mid-1); TreeNode *root = new TreeNode(head->val); head = head->next; TreeNode *rightChild = sortedListToBST(head, mid+1, end); root->left = leftChild; root->right = rightChild; return root; } };

总结：

这个方法非常不容易理解

TreeNode *sortedListToBST(ListNode *&head, int start, int end)

这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.

跑一个例子：

linked list: 0->1->2->NULL

                                                             call (head(0), 0, 2)

                                                                    mid = 1

                                                             node(1), head(2)

                                                /                                               \

                       call (head(0), 0, 0)                                        call (head(2), 2, 2)

                               mid = 0                                                         mid = 2

                       node(0), head(1)                                           node(2), head(NULL)

                        /                    \                                              /                        \

call (head(0), 0, -1)            call (head(0), 1, 0)     call (head(2), 2, 1)          call (head(0), 2, 1)

return NULL                       return NULL               return NULL                    return NULL

最终结果：

    1

  /    \

0      2