LeetCode 109. Convert Sorted List to Binary Search Tree

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 109. Convert Sorted List to Binary Search Tree 原题链接中等

作者：

yxc , 2018-05-17 21:46:52 , 所有人可见 , 阅读 2251

题目描述

给定一个从小到大排序的单链表，请将它转化成一棵平衡二叉树(BST)。

对于这道题目，我们定义一棵平衡二叉树需要满足：任意节点的左右两棵子树的高度差不能大于1。

样例

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

一个可能的答案是：[0,-3,9,-10,null,5], 如下所示：
      0
     / \
   -3   9
   /   /
 -10  5

算法

(递归) $O(n^2)$

这道题目和 Convert Sorted Array to Binary Search Tree 类似，不同点在于找中点时需要遍历，遍历的复杂度是 $O(n)$ ，所以总时间复杂度是 $O(n^2)$ 。

做法：
递归建立整棵二叉树。
每次以中点为根，以左半部分为左子树，右半部分为右子树。先分别递归建立左子树和右子树，然后令根节点的指针分别指向两棵子树。

证明：
我们证明一个更强的结论，该算法得到的BST满足：任意节点的左右子树的所有高度的差不大于1（注意不是最大高度）。
在每一次递归过程中，左半部分的长度最多比右半部分的长度少1，那会不会有这种情况：左半部分的高度分别有 $m - 1, m$ ，右半部分的高度有 $m, m + 1$ ，则当前节点的高度就是 $m, m + 1, m + 2$ （要加上当前根节点这一层，所以都要加1），则此时树的高度差为2，不平衡。
实际上这种情况是不可能的：反证，对于左子树，由于存在高度 $m - 1$ ，所以左半部分最多有 $2^m-2$ 个数；对于右子树，由于存在高度 $m$ 和 $m + 1$ ，所以右半部分最少有 $2^{m}$ 个数，此时左右两部分的数的个数最少差2，矛盾。

时间复杂度分析：一共递归 $O(logn)$ 层，每层的时间复杂度是 $O(n)$ ，所以总时间复杂度是 $O(nlogn)$ 。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return 0;
        int l = 0;
        for (auto i = head; i; i = i->next) l ++ ;
        l /= 2;

        ListNode*p = head;
        for (int i = 0; i < l; i ++ ) p = p->next;
        TreeNode *root = new TreeNode(p->val);

        root->right = sortedListToBST(p->next);
        if (l)
        {
            p = head;
            for (int i = 0; i < l - 1; i ++ ) p = p->next;
            p->next = 0;
            root->left = sortedListToBST(head);
        }
        return root;
    }
};

8 评论

有心人 2021-07-07 16:39

// 方法一： 递归 + 快慢指针找中点：时间O(nlogn), 递归栈空间O(logn)
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;

         // 注意：只有一个结点时这里要特判一下，否则需要在下面再特判
        if (!head->next) return new TreeNode(head->val);

        // 寻找中点，因为要把左半部分链表尾指向空，要存中点前一个结点preSlow
        ListNode *slow = head, *fast = head, *preSlow = nullptr; // 初始化为nullptr时 不能用auto
        while (fast && fast->next) // 结点数至少为2，preSlow至少被赋值一次，不会为null，肯定存在左子树
            preSlow = slow, slow = slow->next, fast = fast->next->next;

        auto root = new TreeNode(slow->val); // slow是中点
        preSlow->next = nullptr; // 建立左子树前，要把 左边链表尾preSlow 指向空
        root->left = sortedListToBST(head); // head 是 左子树根结点
        root->right = sortedListToBST(slow->next); //slow->next 是 右子树根结点      
        return root;
    }
};

// 方法二： 递归 + 中序遍历优化：时间O(n),递归栈空间O(logn)
// 方法一的时间复杂度的瓶颈在于寻找中位数节点，由于构造出的二叉搜索树的中序遍历结果就是链表本身，可利用此进行优化，1pass
class Solution {
public:
    ListNode* h; // h=head作为全局变量，也可以TreeNode* build(ListNode*& head, int l, int r) 中把head加引用作为参数传递

    TreeNode* sortedListToBST(ListNode* head) {
        h = head;
        int n = 0;
        for (auto p = head; p; p = p->next) n++;
        return build(0, n - 1);
    }

    TreeNode* build(int l, int r) {
        if (l > r) return nullptr;
        int mid = (l + r + 1) / 2; // l + r + 1 就和方法一 中点位置一致, 结点为偶数时 中点偏右1个; 不+1也可，中点偏左1个

        TreeNode* root = new TreeNode(); // 只是 简单地创建root，没有赋值，中序遍历的 赋值 应该在 左子树递归之后
        root->left = build(l, mid - 1);         // 左
        root->val = h->val;                     // 中，中序遍历 在此处才应该 对 根节点 进行赋值
        h = h->next; // 维护全局指针h，从链表头结点开始，用h->val 对构建的结点赋值，赋值一次指针后移一位，直到把链表h遍历完
        root->right = build(mid + 1, r);        // 右
        return root;
    }    
};