LeetCode109：有序列表转二叉搜索树

题目描述

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

题目链接：

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

样例

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

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

      0
     / \
   -3   9
   /   /
 -10  5

解题思路及代码

第一、我们要明白什么是BST。题目中描述了，所谓的二叉搜索树是一种对所有结点左右子树深度都不超过1，且左子树值都不超过根结点的值，右子树的值都不小于根结点的值。

第二、明确题目中给出的单链表是升序。

那么，我们无非需要找到单链表中的中间结点的值，然后依次递归迭代的构建出左右子树。

因此，我们重点解决的问题就是从单链表中找到中间结点。

因为是单链表结构，并不是数组结构，所以查找中间结点需要进行遍历查找才行。那么我们是不是可以将单链表结构的数据转换成数组结构呢？这样岂不是查找起来比较容易吗？

由此思路，我们可以先遍历一遍单链表，然后构造出来一个数组，找到中间元素，再迭代构建数组的左右元素即可。具体代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # 采用递归的方式进行求解，由于是已经排序好的单链表，首先获取全部的排序元素值，然后根据取中间元素构建根节点，依次进行递归迭代左右结点即可
        def helper(vals):
            if vals:
                mid = len(vals) // 2
                root = TreeNode(vals[mid])
                root.left = helper(vals[:mid])
                root.right = helper(vals[mid+1:])
                return root
        if not head:
            return
        # 获取所有的元素值
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        return helper(vals)

上述解决问题的思路可以说一种取巧的思路，那么我们能够直接操作单链表来查询中间结点呢？答案是，当然可以。为了直接操作单链表来获取中间结点，我们首先要明确怎么来进行遍历查找。

既然是中间结点，那么就是整个单链表的中间元素，我们如果知道整个链表长度，然后再遍历一次链表取中间长度的岂不是就可以了吗？但是这样势必会花费更多的时间，从而导致效率低下。那我们能否将这遍历的操作放在同一个过程中呢？这样我们就可以一次遍历完成了。因此，我们使用两个指针（也就是双指针法）slow、fast，让slow每次走一步，fast走两步，那么当fast走到尾部的时候，slow刚好走到中间位置。注意：由于后续需要再递归求解左右子树，我们需要将单链表从中间位置断开，这时我们需要一个pre指针来记录slow的前一个位置。具体实现代码如下：

Python版本

# 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 findMiddle(self, head):

        # pre指针用来将左边从中间结点断开
        prev = None
        slow = head
        fast = head

        # 迭代执行直到尾指针到达链表结尾
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        # 从中间结点进行断开
        if prev:
            prev.next = None

        return slow

    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """

        # 如果头结点不存在，直接返回空
        if not head:
            return None

        # 找到中间结点
        mid = self.findMiddle(head)

        # 将中间结点构建成根结点
        node = TreeNode(mid.val)

        # 如果只有一个元素，则直接返回
        if head == mid:
            return node

        # 递归迭代执行，构建左右子树
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(mid.next)
        return node

Java版本

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

喜欢的话点个在看吧👇