109. Convert Sorted List to Binary Search Tree

O(n) time O(logn) space
采用中序遍历思想，先确定链表长度，然后二分递归进行中序遍历
是108. Convert Sorted Array to Binary Search Tree的升级版

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        this->head = head;
        int n = 0;
        for (auto p = head; p; p = p->next) {
            ++n;
        }
        return dfs(0, n);
    }

    TreeNode *dfs(int b, int e) {
        if (b == e) return nullptr;
        int m = b + (e - b) / 2;
        auto l = dfs(b, m);
        auto res = new TreeNode(head->val);
        head = head->next;
        res->left = l;
        res->right = dfs(m + 1, e);
        return res;
    }

    ListNode *head;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        node = head;
        int n = 0;
        for (auto x = head; x; x = x->next) {
            ++n;
        }
        return inorder(0, n - 1);
    }

    TreeNode *inorder(int l, int r) {
        if (l > r) return nullptr;
        int m = l + (r - l) / 2;
        auto left = inorder(l, m - 1); // 采用双闭区间
        auto res = new TreeNode(node->val); // 这一步一定要后于左半边递归，因为node此时并非真正的root，等左半边遍历过以后，node才是root
        node = node->next;
        res->left = left;
        res->right = inorder(m + 1, r);
        return res;
    }

    ListNode *node;
};

O(nlogn) time O(logn) space

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);
        ListNode dummy_head(0), *slow = &dummy_head, *fast = head;
        dummy_head.next = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        auto root = slow->next;
        auto res = new TreeNode(root->val);
        slow->next = nullptr;
        res->left = sortedListToBST(head);
        res->right = sortedListToBST(root->next);
        return res;
    }
};