109. Convert Sorted List to Binary Search Tree

Solution1: use 108, convert to list then do the same.

T: O(2n)

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        return dfs(list, 0, list.size()-1);
    }
    private TreeNode dfs(List<Integer> list, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right)/2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = dfs(list, left, mid-1); 
        root.right = dfs(list, mid + 1, right); 
        return root;
    }
}

solution 2: use slow fast pointer to find mid

and dfs(head, null) to build BS tree

slower than solution1, because needs to find mid every time...

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return dfs(head, null);
    }
    private TreeNode dfs(ListNode begin, ListNode end) {
        if (begin == end) {
            return null;
        }
        ListNode mid = findMid(begin, end); // (5, 9), mid = 5
        TreeNode root = new TreeNode(mid.val); // 5
        root.left = dfs(begin, mid);  // 5,5 -> means it finished
        root.right = dfs(mid.next, end);
        return root;
    }
    private ListNode findMid(ListNode begin, ListNode end) { // exclude end
        ListNode fast = begin;
        ListNode slow = begin;
        while (fast != end && fast.next != end) {
            fast = fast.next.next; // 9
            slow = slow.next; // 0
        }
        return slow;
    }
}

/***

-10 -3 1    0    5 6 9

      0
    /.  \ 
    -3   6
    /\.  /\
  -10 1 5 9

  so it actually asks find max node, then do left part , right part DFS
 */

Solution3: directly uses inorder

T: O(n)

class Solution {
    private ListNode cur;
    public TreeNode sortedListToBST(ListNode head) {
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        this.cur = head;
        return dfs(0, len-1); // still needs len, to control the base case 
    }
    private TreeNode dfs(int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right)/2;

        TreeNode leftTreeNode = dfs(left, mid-1);
        TreeNode root = new TreeNode(cur.val);
        cur = cur.next;

        TreeNode rightTreeNode = dfs(mid+1, right);
        root.left = leftTreeNode;
        root.right = rightTreeNode;
        return root;
    }
}

improved Solution 3

use a class Wrapper to avoid using global variable:

class Solution {
    class ListNodeWrapper {
        private ListNode node;
        ListNodeWrapper(ListNode node) {
            this.node = node;
        }
    }
    public TreeNode sortedListToBST(ListNode head) {
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        return dfs(new ListNodeWrapper(head), 0, len-1); // still needs len, to control the base case 
    }
    private TreeNode dfs(ListNodeWrapper cur, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right)/2;

        TreeNode leftTreeNode = dfs(cur, left, mid-1);
        TreeNode root = new TreeNode(cur.node.val);
        cur.node = cur.node.next;

        TreeNode rightTreeNode = dfs(cur, mid+1, right);
        root.left = leftTreeNode;
        root.right = rightTreeNode;
        return root;
    }
}