题目：有序链表转换二叉搜索树

• 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
• 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5],
它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

来源：力扣（LeetCode）第109题

链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree

分析：

• 递归 + 快慢双指针
  • 使用快慢指针找出链表的中点。
  • 然后将中点生成树的根。
  • 递归进入左右子树。
• 模拟遍历中序二叉树
  • 算出链表的长度
  • 把链表一分为二
  • 递归进入链表的左边和右边
  • 同时，在左边递归完后生成父节点
  • 再把递归得到的左右子节点放在父节点的left和right

代码：

• 递归 + 快慢双指针

  /**
  * 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 {
  public TreeNode sortedListToBST(ListNode head) {
      return recursion(head,null);
  }
  public TreeNode recursion(ListNode point, ListNode end) {
      if (point == end) return null;
      ListNode head = point, fast = point, slow = point;
      while (fast != end && fast.next != end) {slow = slow.next;fast = fast.next.next;}
      TreeNode node = new TreeNode(slow.val);
      node.left = recursion(head, slow);
      node.right = recursion(slow.next, end);
      return node;
  }
  }
  

• 模拟遍历中序二叉树

  /**
  * 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 head;
  
  public TreeNode sortedListToBST(ListNode head) {
      this.head = head;
      int cnt = -1;ListNode tail = head;
      while (tail != null) {cnt++;tail = tail.next;} // 拿到链表的长度
      return recursion(0, cnt);
  }
  
  public TreeNode recursion(int left, int right) {
      if (left > right) return null;
      int mid = (left + right) >> 1;
      TreeNode l = recursion(left, mid - 1);
      TreeNode node = new TreeNode(head.val);
      node.left = l;
      head = head.next;
      node.right = recursion(mid + 1, right);
      return node;
  }
  }
  

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution:
  def sortedListToBST(self, head: ListNode) -> TreeNode:
      self.head = head
      tail = head
      cnt = -1
      while tail:
          cnt += 1
          tail = tail.next;
  
      def recursion(left, right):
          if left > right:
              return
          mid = (left + right) >> 1
          l = recursion(left, mid - 1)
          node = TreeNode(self.head.val)
          self.head = self.head.next
          node.left = l
          node.right = recursion(mid + 1, right)
          return node
      return recursion(0, cnt)