109. Convert Sorted List to Binary Search Tree

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Thoughts

根据有序数组生成对应值的BST。根据BST的定义，中点为当前节点，再递归对数组左边生成左子树和对右边递归生成右子树。如果每次都要找终点，一共lgN层递归，每层遍历全部节点，总时间复杂度O(NlgN)。为了把找中点步骤省掉，用类似Serialize二叉树的思路做中序遍历，用global var记录当前遍历到的节点，并配合[l, r]记录当前遍历的范围。

Code

/*
 * @lc app=leetcode id=109 lang=cpp
 *
 * [109] Convert Sorted List to Binary Search Tree
 */

// @lc code=start
/**
 * 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:
    ListNode *cur = nullptr;
    TreeNode* toBST(int l, int r) {
        if (l > r) return nullptr;
        int mid = l + (r - l) / 2;
        auto left = toBST(l, mid - 1);
        TreeNode *node = new TreeNode(cur->val);
        cur = cur->next;
        node->right = toBST(mid + 1, r);
        node->left = left;
        return node;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        const auto size = [&]() {
            auto cur = head;
            int cnt = 0;
            while (cur != nullptr) {
                ++cnt;
                cur = cur->next;
            }
            return cnt;
        };
        cur = head;
        return toBST(0, size() - 1);
    }
};
// @lc code=end

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

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

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

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        return toBST(head, null);
    }
}