首页 > 代码库 > 算法之 有序链表和平衡二叉树
算法之 有序链表和平衡二叉树
题目描述:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
给定一个有序的链表,要求构建一颗平衡二叉查找树。
解析:二叉查找树的中序遍历的结构就是一颗二叉查找树,要使得最终的二叉查找树的结构尽可能的平衡,也就是说只需要将左右两边的节点数尽可能的均匀,(注意,此处的均匀是一个递归的概念,也就是说每一个节点的左右子树的节点个数都应该尽量均匀)。我们首先想到了二分。
于是下面的代码应运而生:
TreeNode *sortedListToBST(ListNode *head) { if(head == nullptr) return (TreeNode *)nullptr; ListNode *fast=head->next; ListNode *slow=head , *prev= nullptr; while(fast && fast->next) { prev=slow; fast=fast->next->next; slow=slow->next; } //have left tree or not if(prev)prev->next=nullptr; //此处直接将next赋值为空,那么链表的结构便被改变了。 else head=nullptr; TreeNode *node = new TreeNode(slow->val); fast=slow->next; slow->next=nullptr; TreeNode *L = sortedListToBST(head); TreeNode *R = sortedListToBST(fast); node->left=L; node->right=R; return node; }
上述代码虽然可以完成我们需要的平衡二叉查找树,但是上述代码却有一个致命的缺点:那就是内存泄露,
上述代码在执行过程中将原始的链表的节点弄得面目全非,那么也就是说如果那么节点都是通过new操作符得来的话,那么在执行完这个函数之后,有大部分节点的指针已经无法访问到,导致内存泄露。
于是,我们不能使用拆分链表的形式来构建平衡二叉查找树,我们不能改变链表的结构,那么怎么办呢。我们需要做的就是记录当前链表的头结点和长度即可。实现如下:
class Solution { //之前的代码虽然AC了,但是会改变list的结构,这样必导致内存泄露,于是前面的代码全部都是错误的。 private: int Len(ListNode *head) { int ret=0; while(head) { ++ret; head=head->next; } return ret; } TreeNode *helper(ListNode *head, int len) { if(head == nullptr || len <= 0 ) return nullptr; ListNode *cur=head; int mid=(len+1)/2-1; int tmp=mid; while(tmp) { cur=cur->next; --tmp; } TreeNode *root = new TreeNode(cur->val); root->left = helper(head,mid); root->right = helper(cur->next,len-mid-1); return root; } public: TreeNode *sortedListToBST(ListNode *head) { const int n = Len(head); TreeNode *root=helper(head,n); return root; } };
于是上述代码中的内存泄露的问题便消除了,因为在整个过程中我们都没有改变链表的任何节点的指向。
这里,最最值得一提的便是链表的销毁。在销毁链表时,要么使用返回值,要么传入的参数是链表的引用,或者是指针的指针,否则也会有内存的隐患:
也就是说删除链表的代码为:
void destory(ListNode * &head) { ListNode *tmp=nullptr; while(head) { tmp=head->next; delete head; head = nullptr ; //删除指针的额安全的方式,便是delete之后将该指针赋值为空 head=tmp; } head = nullptr; //当然,头结点也不例外,如果传入的参数不是指针的指针或者是引用的话,那么head虽然delete掉了,但是该指针在下一次被赋值之前依然指向内存的某一块区域。 }
算法之 有序链表和平衡二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。