题目描述
给定一个从小到大排序的单链表,请将它转化成一棵平衡二叉树(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;
}
};
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(n^2)$啊?复杂度递推是$T(n)=2T(n/2)+O(n)$吧,应该是$O(nlogn)$?
是的,已修正。
y神,我觉得你求中点的办法略微有点麻烦,可以用快慢指针,快指针到结尾,慢指针则在中间, 1 pass
有道理,更简洁!