Java Recursive Solution


  • 0
    C

    Use the slow and fast pointers to find the mid-point of the list.
    The value of the mid-point of the list will become the root of the tree and
    list on left side, would be the left tree and the list on right would be the right tree.

         public class Solution {
                public TreeNode sortedListToBST(ListNode head) {
                    if(head == null) return null;
                    return toBST(head,null);
                }
                 public TreeNode toBST(ListNode head,ListNode tail)
                 {
                    if(head == tail) return null;
                    ListNode slow = head;
                    ListNode fast = head;
                    while(fast!=tail && fast.next != tail)
                    {
                        slow = slow.next;
                        fast = fast.next.next;
                    }
                    TreeNode node = new TreeNode(slow.val);
                    node.left = toBST(head,slow);
                    node.right = toBST(slow.next,tail);
                    return node;
                 }
            }

  • 0
    S

    why you need a tail? Not that understand.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.