109.Convert-Sorted-List-to-Binary-Search-Tree

109. Convert Sorted List to Binary Search Tree

题目地址

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

https://www.lintcode.com/problem/convert-sorted-list-to-binary-search-tree/description

https://www.jiuzhang.com/solutions/convert-sorted-list-to-balanced-bst/

题目描述

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
     / \
   -3   9
   /   /
 -10  5

代码

Approach #1

/**
 * 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; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;

    return helper(head);
  }

  private TreeNode helper(ListNode head) {
    if (head == null) return null;

    if (head.next == null) return new TreeNode(head.val);

    // cut the list in two
    ListNode pre = null;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
      pre = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    pre.next = null;

    // binary
    TreeNode root = new TreeNode(slow.val);
    TreeNode L = helper(head);
    TreeNode R = helper(slow.next);
    root.left = L;
    root.right = R;

    return root;
  }

}

Approach solution 2:

public class Solution {
    private int getListLength(ListNode head) {
    int len = 0;
    while (head != null) {
      len++;
      head = head.next;
    }
    return len;
  } 

  public TreeNode sortedListToBST(ListNode head) {
    ListNode current = head;
    int len = getListLength(current);
    return helper(head, len);
  }

  public TreeNode helper(int len) {
    if (len <= 0) return null;

    TreeNode left = helper(len / 2);
    TreeNode root = new TreeNode(head.val);
    head = head.next;
    TreeNode right = helper(len - 1 - len / 2);

    root.left = left;
    root.right = right;

    return root;
 }

Approach #3 Recursion + Conversion to Array

class Solution {

  private List<Integer> values;

  public Solution() {
    this.values = new ArrayList<Integer>();
  }

  private void mapListToValues(ListNode head) {
    while (head != null) {
      this.values.add(head.val);
      head = head.next;
    }
  }

  private TreeNode convertListToBST(int left, int right) {
    // Invalid case
    if (left > right) {
      return null;
    }

    // Middle element forms the root.
    int mid = (left + right) / 2;
    TreeNode node = new TreeNode(this.values.get(mid));

    // Base case for when there is only one element left in the array
    if (left == right) {
      return node;
    }

    // Recursively form BST on the two halves
    node.left = convertListToBST(left, mid - 1);
    node.right = convertListToBST(mid + 1, right);
    return node;
  }

  public TreeNode sortedListToBST(ListNode head) {

    // Form an array out of the given linked list and then
    // use the array to form the BST.
    this.mapListToValues(head);

    // Convert the array to
    return convertListToBST(0, this.values.size() - 1);
  }
}