有序链表转换二叉搜索树

本题思路不难，由于链表本身已经有序了，根据二叉搜索树的性质，每次在当前的链表找到中点作为当前树的根节点，再将链表分割并递归构造子树。

同时在寻找链表中点的时候采用快慢指针提高速度。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        TreeNode* T = buildTree(head); 
        return T;
    }
    TreeNode* buildTree(ListNode* head){
        if(!head){
            return NULL; 
        }
        if(!head->next){
            TreeNode* T = new TreeNode(head->val); 
            return T;
        }
        ListNode* mid = findMid(head); 
        TreeNode* T = new TreeNode(mid->val); 
        ListNode* p = head; 
        // NULL放在右边进行比较，不能作为一个表达式放在左边比较
        while(p->next!=mid){
            p = p->next; 
        }
        p->next = NULL;
        ListNode* r = mid->next; 
        T->left = buildTree(head); 
        if(r){
            T->right = buildTree(r); 
        }
        return T;
    }
    ListNode* findMid(ListNode* head){
        ListNode* slow = head; 
        ListNode* fast = head; 
        while(fast!=NULL  &&  fast->next!=NULL){
            slow = slow->next; 
            fast = fast->next->next; 
        }
        return slow; 
    }
};


时间复杂度：$o(nlogn)$按照常规的分治算法复杂度来计算
空间复杂度：$o(n)$每次递归调用产生一个节点，一共n个节点，每次递归调用为常数级空间复杂度。

109. 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
      0
     / \
   -3   9
   /   /
 -10  5

 
class Solution {
     public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        else if(head.next == null) return new TreeNode(head.val);
        ListNode pre = head;
        ListNode p = pre.next;
        ListNode q = p.next;
        //找到链表的中点p
        while(q!=null && q.next!=null){
            pre = pre.next;
            //p走一倍的速度
            p = pre.next;
            //q走两倍的速度
            q = q.next.next;
        }
        //将中点左边的链表分开
        pre.next = null;
        TreeNode root = new TreeNode(p.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(p.next);
        return root;
    }
}

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

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

题目链接
/**
 * 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) {
        return helper(head, null);
    }

    public TreeNode helper(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right); // 获取中间节点
        TreeNode root = new TreeNode(mid.val);
        root.left = helper(left, mid);
        root.right = helper(mid.next, right);
        return root;
    }
    // 根据快慢指针获取中间节点
    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

同该题解法大致相同，这里主要找出链表的中间节点即可。这里通过设置快慢指针来达到寻找中间节点的效果。详细请看代码，有疑问欢迎留言。

目录
题目描述
题目大意
解题方法
题目描述
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
  0
 / \

-3   9

/   /

-10  5
题目大意
将一个有序得单链表，转换为高度平衡的二叉搜索树。
二叉搜索树定义：（Binary Search Tree）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
高度平衡二叉树定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
解题方法
首先：确定根节点

根据二叉搜索树的性质我们将选择链表元素的中位数作为根节点的值。
这里对于中位数的定义为：如果链表中的元素个数为奇数，那么唯一的中间值为中位数；如果元素个数为偶数，那么唯二的中间值都可以作为中位数，而不是常规定义中二者的平均值。
根据中位数的性质，链表中小于中位数的元素个数与大于中位数的元素个数要么相等，要么相差 11。此时，小于中位数的元素组成了左子树，大于中位数的元素组成了右子树，它们分别对应着有序链表中连续的一段。

在这之后，使用分治的思想，继续递归地对左右子树进行构造，找出对应的中位数作为根节点，以此类推。
分治

具体地，设当前链表的左端点为 left，右端点right，包含关系为「左闭右开」，即 left 包含在链表中而 right 不包含在链表中。我们希望快速地找出链表的中位数节点 mid。
为什么要设定「左闭右开」的关系？由于题目中给定的链表为单向链表，访问后继元素十分容易，但无法直接访问前驱元素。因此在找出链表的中位数节点 mid 之后，如果设定「左闭右开」的关系，我们就可以直接用(left,mid) 以及 (mid.next,right) 来表示左右子树对应的列表了。并且，初始的列表也可以用(head,null) 方便地进行表示，其中null 表示空节点。
找出链表中位数节点的方法多种多样，其中较为简单的一种是**「快慢指针法」**。初始时，快指针fast 和慢指针 \textit{slow}slow 均指向链表的左端点left。我们将快指针fast 向右移动两次的同时，将慢指针 slow 向右移动一次，直到快指针到达边界（即快指针到达右端点或快指针的下一个节点是右端点）。此时，慢指针对应的元素就是中位数。
在找出了中位数节点之后，我们将其作为当前根节点的元素，并递归地构造其左侧部分的链表对应的左子树，以及右侧部分的链表对应的右子树。
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def getMedian(left: ListNode, right: ListNode) -> ListNode:
            fast = slow = left
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow
        
        def buildTree(left: ListNode, right: ListNode) -> TreeNode:
            if left == right:
                return None
            mid = getMedian(left, right)
            root = TreeNode(mid.val)
            root.left = buildTree(left, mid)
            root.right = buildTree(mid.next, right)
            return root
        
        return buildTree(head, None)

复杂度分析

时间复杂度：O(nlogn)，其中 n 是链表的长度。

设长度为 n 的链表构造二叉搜索树的时间为 T(n)，递推式为 T(n)=2⋅T(n/2)+O(n)，根据主定理，T(n)=O(nlogn)。

空间复杂度：O(logn)，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(logn)，即为递归过程中栈的最大深度，也就是需要的空间。
2020-08-18