FilesExpand file tree

 master

/

ConvertSortedListtoBinarySearchTree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

29 lines (28 loc) · 869 Bytes

 master

/

ConvertSortedListtoBinarySearchTree.java

Copy path

Top

File metadata and controls

• Code
• Blame

29 lines (28 loc) · 869 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

/**

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

* balanced BST.

*/

public class ConvertSortedListtoBinarySearchTree {

public TreeNode sortedListToBST(ListNode head) {

return sortedListToBST(head, null);

}

private TreeNode sortedListToBST(ListNode start, ListNode end) {

if (start == end) {

return null;

} else if (start.next == end) {

return new TreeNode(start.val);

} else {

ListNode fast = start, slow = start;

while (fast.next != end && fast.next.next != end) {

fast = fast.next.next;

slow = slow.next;

}

TreeNode left = sortedListToBST(start, slow);

TreeNode right = sortedListToBST(slow.next, end);

TreeNode root = new TreeNode(slow.val);

root.left = left;

root.right = right;

return root;

}

}

}