1. Description

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

2. Example

Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5

3. Code

public class LeetCode0109 {

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private ListNode current;

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        int size = 0;
        current = head;
        for (ListNode p = head; p != null; p = p.next) {
            size++;
        }

        return dfs(head, size);
    }

    private TreeNode dfs(ListNode head, int size) {

        if (size == 0) {
            return null;
        }

        TreeNode left = dfs(head, size / 2);
        TreeNode root = new TreeNode(current.val);
        current = current.next;
        TreeNode right = dfs(head, size - size / 2 - 1);
        root.left = left;
        root.right = right;
        return root;
    }
}