鏈表 有序鏈表轉(zhuǎn)換二叉搜索樹

題目

給定一個(gè)單鏈表，其中的元素按升序排序，將其轉(zhuǎn)換為高度平衡的二叉搜索樹。

本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過 1。

示例:

給定的有序鏈表： [-10, -3, 0, 5, 9],

一個(gè)可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個(gè)高度平衡二叉搜索樹：

      0
     / \
   -3   9
   /   /
 -10  5

解題

/**
 * 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; } }
 */
class Solution {


  private ListNode findMiddleElement(ListNode head) {


    // The pointer used to disconnect the left half from the mid node.
    ListNode prevPtr = null;
    ListNode slowPtr = head;
    ListNode fastPtr = head;


    // Iterate until fastPr doesn't reach the end of the linked list.
    while (fastPtr != null && fastPtr.next != null) {
      prevPtr = slowPtr;
      slowPtr = slowPtr.next;
      fastPtr = fastPtr.next.next;
    }


    // Handling the case when slowPtr was equal to head.
    if (prevPtr != null) {
      prevPtr.next = null;
    }


    return slowPtr;
  }


  public TreeNode sortedListToBST(ListNode head) {


    // If the head doesn't exist, then the linked list is empty
    if (head == null) {
      return null;
    }


    // Find the middle element for the list.
    ListNode mid = this.findMiddleElement(head);


    // The mid becomes the root of the BST.
    TreeNode node = new TreeNode(mid.val);


    // Base case when there is just one element in the linked list
    if (head == mid) {
      return node;
    }


    // Recursively form balanced BSTs using the left and right halves of the original list.
    node.left = this.sortedListToBST(head);
    node.right = this.sortedListToBST(mid.next);
    return node;
  }
}