109 Convert Sorted List to Binary Search Tree

每次取中点元素，新建成为新的二叉树。迭代

Python

# 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 head:
            pre = None
            slow, fast = head, head
            while fast and fast.next:
                pre = slow
                slow = slow.next
                fast = fast.next.next
            root = TreeNode(slow.val)
            if pre:
                pre.next = None
                root.left = self.sortedListToBST(head)
                root.right = self.sortedListToBST(slow.next)
            return root

Java

/**
 * 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 {
    public TreeNode sortedListToBST(ListNode head) {
        return this.toBSTRecursive(head, null);
    }
    private TreeNode toBSTRecursive(ListNode start,ListNode end){
        if(start == end){
            return null;
        }
        else{
            ListNode mid = start;
            ListNode fast = start;
            while(fast != end && fast.next != end){
                mid = mid.next;
                fast = fast.next.next;
            }
            TreeNode root = new TreeNode(mid.val);
            root.left = this.toBSTRecursive(start, mid);
            root.right = this.toBSTRecursive(mid.next, end);
            return root;
        }
    }
}