Leetcode-每日一题【109.有序链表转换二叉搜索树】

题目

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

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

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

提示:

head 中的节点数在[0, 2 * 104] 范围内
-105 <= Node.val <= 105

解题思路

前置知识

二叉搜索树又称二叉排序树，具有以下性质：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

注意：二叉搜索树中序遍历的结果是有序的

知道了什么是二叉搜索树，我们怎样将有序链表转换为二叉搜索树呢？

1.要想将有序链表转换为二叉搜索树，我们先观察一下二叉搜索树会发现根节点的左子树上的节点均小于根节点，而根节点又子树上的节点均大于根节点，那么在有序链表中能满足这个条件的节点就是我们链表的中间节点，所以我们要找出链表的中间节点（详细讲解请看【876.链表的中间结点】）同时我们要在查找中间节点的过程中设置一个pre节点来存储我们中间节点的前一个节点。

2.找到中间节点low和中间节点的前一个结点pre后，我们将链表分隔为中间节点、中间节点之前的链表、中间节点之后的链表、

3.然后设置一个TreeNode root 让他的值等于中间节点 low 的值，再递归的去转换中间节点之前的链表和中间节点之后的链表。最后返回 root 即可。

代码实现

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            TreeNode root = new TreeNode(head.val);
            return root;
        }
        ListNode fast = head;
        ListNode low = head;
        ListNode pre = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            pre = low;
            low = low.next;
        }
        pre.next = null;
        ListNode rightList = low.next;
        TreeNode root = new TreeNode(low.val);
        root.right = sortedListToBST(rightList);
        root.left = sortedListToBST(head);
        return root;

    }
}