leetcode -- 109. Convert Sorted List to Binary Search Tree

题目描述

题目难度：Medium
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.

AC代码

leetcode上优秀解法

/**
 * 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 ListNode node;

public TreeNode sortedListToBST(ListNode head) {
	if(head == null){
		return null;
	}
	
	int size = 0;
	ListNode runner = head;
	node = head;
	
	while(runner != null){
		runner = runner.next;
		size ++;
	}
	
	return inorderHelper(0, size - 1);
}

public TreeNode inorderHelper(int start, int end){
	if(start > end){
		return null;
	}
	
	int mid = start + (end - start) / 2;
	TreeNode left = inorderHelper(start, mid - 1);
	
	TreeNode treenode = new TreeNode(node.val);
	treenode.left = left;
	node = node.next;

	TreeNode right = inorderHelper(mid + 1, end);
	treenode.right = right;
	
	return treenode;
}
}