109. 有序链表转换二叉搜索树（BST）

109. 有序链表转换二叉搜索树

• 题目
• 解题思路
• 代码

题目

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

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

解题思路

本题和 108 一样，只要将通过数组索引定位中心元素改成快慢指针法找中心元素即可

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
      ListNode p = head, q = head, pre = null;
        //base case
       if (head == null) {//head为空，就是空树
            return null;
        }
        if (head.next == null) {//head只有一个节点，返回head
            return new TreeNode(head.val);
        }
         // 快慢指针找中心节点
        while (q != null && q.next != null) {//快指针==null，即到达了链表尾部，这时候慢指针刚好到达链表中间位置，可以自己举例试试，因为快指针一次走两步，慢的一次走一步
            pre = p;//保存慢指针之前的那个值，因为到时候慢指针就是中间，pre就是左子树
            p = p.next;
            q = q.next.next;
        }
        pre.next = null;//这句话是用来切割链表的，将head从pre切开,head变为pre左边部分,p为pre右边部分。
       
        // 以升序链表的中间元素作为根节点 root，递归的构建 root 的左子树与右子树。
        TreeNode root = new TreeNode(p.val);
         root.left = sortedListToBST(head);//左子树，因为head已经被pre给切割了，只要遍历到pre.next是null，就会返回null。这样就保证了只有左子树
         root.right = sortedListToBST(p.next); //右子树
        return root;

    }

   


}