题目内容

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

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

示例

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

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

题解

本题与上一题有相似之处，即均需要转化为高度平衡的二叉搜索树。但不同点在于，数组对于取中点这个操作是O(1)的时间复杂度，而取链表的重点则是O(n)的时间复杂度。这里有个取巧的办法就是将链表转化为数组，然后代码与上一题的代码完全一致，因此这里不讲。这里，还是按照上一题的思路直接去实现。

具体，请看代码注释。

代码

/**
 * 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) {
        if(!head) return nullptr;//当节点为空，则直接返回空即可
        int n = 0;//定义链表长度n
        for(auto p = head;p;p=p->next) n++;//计算链表的长度
        if(n==1) return new TreeNode(head->val);//如果n为1，则直接返回一个节点即可。
        auto cur = head;//定义一个当前点，之后全部操作当前点即可
      	/**
      	 * 当链表长度大于1之后，我们让左子树的部分不空更加容易处理。
      	 * 那具体应该遍历多少次呢？
      	 * 左边应该有A = (n-1)/2向上取整的数量，右边应该有B = n-1-A的数量
      	 * 又因为有数学公式：b/a上取整 = (b+a-1)/a下取整
      	 * 因此最后遍历的次数应该为n/2到中点，但又因为我们要将中点的前一个点的next置为空，因此遍历到n/2-1即可。
      	 */
        for(int i = 0; i < n / 2 - 1; i++)cur = cur->next;
      	//根据中点的值创建根节点
        auto root = new TreeNode(cur->next->val);
      	//先遍历右边，因为如果将中点之前的点的next置空，右边的链条就找不到了，因此先把右边的处理了再处理左边。
        root->right = sortedListToBST(cur->next->next);
        cur->next = nullptr;
      	//处理左边
        root->left = sortedListToBST(head);
        return root;
    }
};