Link to LeetCode Problem

S1: 递归+分治

前置知识：

• 二叉搜索树的中序遍历刚好是一个有序序列
• 寻找链表中点
• 分治构建二叉树

具体实现：

1. 构建二叉树要从 root 开始，而二叉搜索树和有序链表的联系就是，二叉搜索树的 root 刚好是有序链表的中点。
2. 将有序链表从中点一分为二，再回到第一步。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return sortedListToBST(head, nullptr);
    }
    TreeNode* sortedListToBST(ListNode* head, ListNode* tail) {
        if (head == tail) return nullptr;

        ListNode* mid = findMidNode(head, tail);
        TreeNode* root = new TreeNode(mid->val);
        root->left = sortedListToBST(head, mid);
        root->right = sortedListToBST(mid->next, tail);
        return root;
    }
    ListNode* findMidNode(ListNode* head, ListNode* tail) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function (head, tail = null) {
  if (!head || head === tail) return null;

  let slow = head,
    fast = head;
  while (fast !== tail && fast.next !== tail) {
    slow = slow.next;
    fast = fast.next.next;
  }

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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head: return None
        prev, slow, fast = None, head, head

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        root = TreeNode(slow.val)
        if slow == fast: return root

        if prev: prev.next = None
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

• Time: $O(NlogN)$，N 是链表长度。递推关系式参照 主定律。以下是个人胡乱分析，寻找链表中间节点的总时间是 $N+2*\frac{N}{2}+4*\frac{N}{4}...+N*1$，由于每次链表长度折半的时候，函数规模都倍增了，所以每一层递归函数寻找链表的总时间还是 N，一共有 logN 层，结果就是 $NlogN$。
• Space: $O(logN)$，递归栈的深度，因为采用了二分的方式来构建树，递归栈的深度最大就是 $log(N)$。

S2: 分治+中序遍历

利用有序链表是搜索二叉树中序遍历结果这一点。先用空节点当 placeholder 来建树，然后在对树进行中序遍历的过程中填充空节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int n = 0;
        ListNode*p = head;
        while (p != nullptr) {
            p = p->next;
            n++;
        }
        return inorder(head, 0, n - 1);
    }
    TreeNode* inorder(ListNode*& head, int start, int end) {
        if (start > end) return nullptr;
        int mid = (start + end + 1) / 2;

        TreeNode* root = new TreeNode();
        root->left = inorder(head, start, mid - 1);
        root->val = head->val;
        head = head->next;
        root->right = inorder(head, mid + 1, end);
        return root;
    }

};

• Time: $O(N)$，N 是链表长度。
• Space: $O(logN)$，递归栈的深度。