Difficulty: Medium

Related Topics: Linked List, Depth-first Search

Given the head of 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 1:

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

  1. Input: head = [-10,-3,0,5,9]
  2. Output: [0,-3,9,-10,null,5]
  3. Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

  1. Input: head = []
  2. Output: []

Example 3:

  1. Input: head = [0]
  2. Output: [0]

Example 4:

  1. Input: head = [1,3]
  2. Output: [3,1]

Constraints:

  • The number of nodes in head is in the range [0, 2 * 10<sup>4</sup>].
  • -10^5 <= Node.val <= 10^5

Solution

Language: Java

  1.  *     ListNode(int val) { this.val = val; }
  2.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  3.  * }
  4.  */
  5. /**
  6.  * Definition for a binary tree node.
  7.  * public class TreeNode {
  8.  *     int val;
  9.  *     TreeNode left;
  10.  *     TreeNode right;
  11.  *     TreeNode() {}
  12.  *     TreeNode(int val) { this.val = val; }
  13.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  14.  *         this.val = val;
  15.  *         this.left = left;
  16.  *         this.right = right;
  17.  *     }
  18.  * }
  19.  */
  20. class Solution {
  22.     public TreeNode sortedListToBST(ListNode head) {
  23.         return dfs(head, null);
  24.     }
  26.     /*
  27.     二分查找的步骤就是一颗 BST，所以可以使用二分查找来生成 BST
  28.     NOTE: 通过二分查找生成的 BST 必定平衡的
  30.     二分查找有两种实现方法
  31.     1. https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure
  32.     2. https://en.wikipedia.org/wiki/Binary_search_algorithm#Alternative_procedure
  34.     这里使用第二种方法方便一些
  35.     */
  36.     private TreeNode dfs(ListNode lo, ListNode hi) {
  37.         if (lo == hi) return null;
  39.         ListNode mid = mid(lo, hi);
  41.         TreeNode root = new TreeNode(mid.val);
  42.         root.left = dfs(lo, mid);
  43.         root.right = dfs(mid.next, hi);
  45.         return root;
  46.     }
  48.     // 通过双指针技巧获得 mid 节点
  49.     // slow 指针一次走一步
  50.     // fast 指针一次走两步
  51.     // 如果链表没有环的话，那么在 fast 走到终点时，slow 一定在中间
  52.     private ListNode mid(ListNode node, ListNode last) {
  53.         ListNode slow = node;
  54.         ListNode fast = node;
  56.         while(fast != last && fast.next != last) {
  57.             slow = slow.next;
  58.             fast = fast.next.next;
  59.         }
  61.         return slow;
  62.     }
  63. }