109. 有序链表转换二叉搜索树

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

解法一：中序遍历

利用二叉搜索树中序遍历为结果为增序的特性，中序遍历构造树，每次顺序访问链表即可。

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

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

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        runner = head      
        length = 0
        while runner:   #求链长
            length += 1
            runner = runner.next
        self.node = head    #链表工作指针
        return self.helper(0, length-1)
    
    def helper(self, start, end):   #把链表看做数组，start为第一个结点，end为最后一个
        if start > end: #递归出口
            return
        mid = start + (end-start) // 2  #求中点
        #其实就是中序遍历格式
        left = self.helper(start, mid-1)    #以中点为界划分左区间
        #以当前节点值创建根，然后工作指针后移
        root = TreeNode(self.node.val)
        self.node = self.node.next   
        right = self.helper(mid+1, end)     #以中点为界划分右区间
        
        root.left, root.right = left, right    #连接根与左右子树
        return root

js:

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    var helper = function(start, end) {
        if (start > end) return null
        const mid = start + parseInt((end - start) / 2)
        const left = helper(start, mid-1)
        const root = new TreeNode(node.val)
        node = node.next
        const right = helper(mid+1, end)
        root.left = left
        root.right = right
        return root
    }
    let runner = head, length = 0
    while(runner) {
        length++
        runner = runner.next
    }
    let node = head
    return helper(0, length-1)
};