Untitled
class Solution { // Definition for singly-linked list. static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; this.next = null; } } // Definition for a binary tree node. static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; } } public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } if (head.next == null) { return new TreeNode(head.val); } // Find the middle node and make it the root ListNode slow = head; ListNode fast = head; ListNode slowPrev = null; while (fast != null && fast.next != null) { slowPrev = slow; slow = slow.next; fast = fast.next.next; } // Disconnect the left half from the middle node if (slowPrev != null) { slowPrev.next = null; } TreeNode root = new TreeNode(slow.val); // Make root root.left = sortedListToBST(head); // Build left subtree root.right = sortedListToBST(slow.next); // Build right subtree return root; } }
Leave a Comment