題目描述（中等難度）

和 108 題 是一樣的，都是給定一個升序序列，然后生成二分平衡查找樹。區(qū)別在于 108 題給定的是數(shù)組，這里給的是鏈表。

解法一

大家先看一下 108 題 吧，算法的關鍵是取到中間的數(shù)據(jù)做為根節(jié)點。而這里鏈表的話，由于不支持隨機訪問，所以會麻煩些。最簡單的思路就是我們把鏈表先用線性表存起來，然后題目就轉換成 108 題了。

為了方便，把上一道題的數(shù)組參數(shù)改為List 。

public TreeNode sortedListToBST(ListNode head) {
    ArrayList<Integer> nums = new ArrayList<>();
    while (head != null) {
        nums.add(head.val);
        head = head.next;
    }
    return sortedArrayToBST(nums);
}

public TreeNode sortedArrayToBST(ArrayList<Integer> nums) {
    return sortedArrayToBST(nums, 0, nums.size());
}

private TreeNode sortedArrayToBST(ArrayList<Integer> nums, int start, int end) {
    if (start == end) {
        return null;
    }
    int mid = (start + end) >>> 1;
    TreeNode root = new TreeNode(nums.get(mid));
    root.left = sortedArrayToBST(nums, start, mid);
    root.right = sortedArrayToBST(nums, mid + 1, end);
    return root;
}

時間復雜度：O(n)。

空間復雜度：數(shù)組進行輔助，O(n)。

解法二

參考 這里。

有沒有一種方案，不用數(shù)組的輔助呢？那么我們需要解決怎么得到 mid 的值的問題。

最直接的思路就是根據(jù) start 和 end，求出 mid，然后從 head 遍歷 mid - start 次，就到達了 mid 值。但最開始的 end，我們還得遍歷一遍鏈表才能得到，總體來說就是太復雜了。

這里有一個求中點節(jié)點值的技巧，利用快慢指針。

快指針和慢指針同時從頭部開始遍歷，快指針每次走兩步，慢指針每次走一步，當快指針走到鏈表尾部，此時慢指針就指向了中間位置。

除了求中點節(jié)點的值不一樣，基本架構和 108 題 是一樣的。

public TreeNode sortedListToBST(ListNode head) {
    return sortedArrayToBST(head, null);
}

private TreeNode sortedArrayToBST(ListNode head, ListNode tail) {
    if (head == tail) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != tail && fast.next != tail) {
        slow = slow.next;
        fast = fast.next.next;
    }

    TreeNode root = new TreeNode(slow.val);
    root.left = sortedArrayToBST(head, slow);
    root.right = sortedArrayToBST(slow.next, tail); 
    return root;
}

時間復雜度：根據(jù)遞歸式可知，T(n) = 2 * T（n / 2 ) + n，O(nlog(n))。

空間復雜度：O(log(n))。

解法三

解法二雖然沒有借助數(shù)組，優(yōu)化了空間復雜度，但是時間復雜度增加了，那么有沒有一種兩全其美的方法，時間復雜度是解法一，空間復雜度是解法二。還真有，參考 這里。

主要思想是，因為我們知道題目給定的升序數(shù)組，其實就是二叉搜索樹的中序遍歷。那么我們完全可以按照這個順序去為每個節(jié)點賦值。

實現(xiàn)的話，我們套用中序遍歷的遞歸過程，并且將 start 和 end 作為遞歸參數(shù)，當 start == end 的時候，就返回 null。

先回想一下中序遍歷的算法。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    getAns(root, ans);
    return ans;
}

private void getAns(TreeNode node, List<Integer> ans) {
    if (node == null) {
        return;
    }
    getAns(node.left, ans); 
    ans.add(node.val);
    getAns(node.right, ans);
}

之前是將 node.val 進行保存，這里的話我們是給當前節(jié)點進行賦值，為了依次賦值，我們需要一個cur指針指向給定的數(shù)列，每賦一個值就進行后移。

ListNode cur = null;

public TreeNode sortedListToBST(ListNode head) {
    cur = head;
    int end = 0;
    while (head != null) {
        end++;
        head = head.next;
    }
    return sortedArrayToBSTHelper(0, end);
}

private TreeNode sortedArrayToBSTHelper(int start, int end) {
    if (start == end) {
        return null;
    }
    int mid = (start + end) >>> 1;
    //遍歷左子樹并且將根節(jié)點返回
    TreeNode left = sortedArrayToBSTHelper(start, mid);
    //遍歷當前根節(jié)點并進行賦值
    TreeNode root = new TreeNode(cur.val);
    root.left = left;
    cur = cur.next; //指針后移，進行下一次的賦值
    //遍歷右子樹并且將根節(jié)點返回
    TreeNode right = sortedArrayToBSTHelper(mid + 1, end);
    root.right = right;
    return root;
}

時間復雜度：O(n)，主要是得到開始的 end，需要遍歷一遍鏈表。

空間復雜度：O(log(n))，遞歸壓棧的消耗。

總

快慢指針求鏈表的中間值，這個技巧不錯。此外，解法三的模仿中序遍歷的過程，然后把給定的數(shù)組依次賦值過去，太強了。

更多詳細通俗題解詳見 leetcode.wang 。