109. Convert Sorted List to Binary Search Tree
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.
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 / \ -39 // -105
難度:medium
題目:給定一個單鏈表其元素為升序排列,將其轉換成高度平衡的二叉搜尋樹
思路:中序遍歷
Runtime: 1 ms, faster than 99.17% of Java online submissions for Convert Sorted List to Binary Search Tree.
Memory Usage: 41 MB, less than 9.56% of Java online submissions for Convert Sorted List to Binary Search Tree.
/** * 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) { if (null == head) { return null; } ListNode ptr = head; int count = 0; for (; ptr != null; ptr = ptr.next, count++); ListNode[] headList = {head}; return sortedListToBST(headList, 0, count - 1); } public TreeNode sortedListToBST(ListNode[] head, int start, int end) { if (start > end) { return null; } int mid = start + (end - start) / 2; TreeNode left = sortedListToBST(head, start, mid - 1); TreeNode root = new TreeNode(head[0].val); root.left = left; head[0] = head[0].next; root.right = sortedListToBST(head, mid + 1, end); return root; } }