题目描述
给定一个从小到大排序的单链表,请将它转化成一棵平衡二叉树(BST)。
对于这道题目,我们定义一棵平衡二叉树需要满足:任意节点的左右两棵子树的高度差不能大于1。
样例
给定有序单链表:[-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5], 如下所示:
0
/ \
-3 9
/ /
-10 5
算法
(递归) O(n2)
这道题目和 Convert Sorted Array to Binary Search Tree 类似,不同点在于找中点时需要遍历,遍历的复杂度是 O(n),所以总时间复杂度是 O(n2)。
做法:
递归建立整棵二叉树。
每次以中点为根,以左半部分为左子树,右半部分为右子树。先分别递归建立左子树和右子树,然后令根节点的指针分别指向两棵子树。
证明:
我们证明一个更强的结论,该算法得到的BST满足:任意节点的左右子树的所有高度的差不大于1(注意不是最大高度)。
在每一次递归过程中,左半部分的长度最多比右半部分的长度少1,那会不会有这种情况:左半部分的高度分别有 m−1,m,右半部分的高度有 m,m+1,则当前节点的高度就是 m,m+1,m+2(要加上当前根节点这一层,所以都要加1),则此时树的高度差为2,不平衡。
实际上这种情况是不可能的:反证,对于左子树,由于存在高度 m−1,所以左半部分最多有 2m−2 个数;对于右子树,由于存在高度 m 和 m+1,所以右半部分最少有 2m 个数,此时左右两部分的数的个数最少差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;
}
};
// 方法一: 递归 + 快慢指针找中点:时间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; } };
y总,上面的时间复杂度为什么开始是N方,下面又是nlogn了啊
y总,if (l)
{
p = head;
for (int i = 0; i < l - 1; i ++ ) p = p->next;
p->next = 0;
}
这里可以改成让p为空吗,为啥还要重新遍历呢?
你是说直接写
p = 0
吗,这样写只能修改p
这个变量的值,不能改变链表中对应节点的next指针。y总,为啥复杂度是O(n2)啊?复杂度递推是T(n)=2T(n/2)+O(n)吧,应该是O(nlogn)?
是的,已修正。
y神,我觉得你求中点的办法略微有点麻烦,可以用快慢指针,快指针到结尾,慢指针则在中间, 1 pass
有道理,更简洁!