给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST）
[编程题]有序链表变成二叉搜索树
思路：这道题是要求把有序链表转为二叉搜索树，和之前那道Convert Sorted Array to Binary Search Tree思路完全一样，只不过是操作的数据类型有所差别，一个是数组，一个是链表。数组方便就方便在可以通过index直接访问任意一个元素，而链表不行。由于二分查找法每次需要找到中点，而链表的查找中间点可以通过快慢指针来操作。找到中点后，要以中点的值建立一个数的根节点，然后需要把原链表断开，分为前后两个链表，都不能包含原中节点，然后再分别对这两个链表递归调用原函数，分别连上左右子节点即可。
public TreeNode sortedListToBST(ListNode head) {
return toBST(head, null);
}
private TreeNode toBST(ListNode head, ListNode tail) {
if (head == tail)
return null;
// 申请两个指针，fast移动速度是low的两倍
ListNode fast = head;
ListNode slow = head;
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = toBST(head, slow);
root.right = toBST(slow.next, tail);
return root;
}
编辑于 2017-08-13 09:59:35
回复(13)
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
if(head.next == null) return new TreeNode(head.val);
ListNode mid = head;
ListNode end = head;
ListNode preMid = null;
while (end != null && end.next != null) {
preMid = mid;
mid = mid.next;
end = end.next.next;
}
TreeNode root = new TreeNode(mid.val);
preMid.next = null;
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
}
编辑于 2016-11-17 18:12:54
回复(7)
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
return BST(head,NULL);
}
TreeNode *BST(ListNode *head,ListNode *tail)
{
if(head == tail)
return NULL;
ListNode *s = head;
ListNode *f = head;
while(f!=tail && f->next!=tail)
{
s = s->next;
f = f->next->next;
}
TreeNode *root = new TreeNode(s->val);
root->left = BST(head,s);
root->right = BST(s->next,tail);
return root;
}
};
发表于 2017-09-12 01:05:23
回复(1)
/*思路：
1.遍历链表得到链表长度
2.根据链表长度构建树
3.先序遍历树填充value */
public class Solution {
ListNode node;
public TreeNode sortedListToBST(ListNode head) {
int count = 0;
ListNode node = head;
//计算链表长度
while(node!=null){
count ++;
node = node.next;
}
if(count == 0)
return null;
//根据count 构建树
TreeNode root = buildTree(count);
this.node = head;
//填充value
alterValue(root);
return root;
}
private TreeNode buildTree(int count){
if(count==0)
return null;
count --;
TreeNode node = new TreeNode(0);
int left = count%2 == 1 ? count/2+1 : count/2;
int right = count/2;
node.left = buildTree(left);
node.right = buildTree(right);
return node;
}
private void alterValue(TreeNode root){
if(root == null)
return ;
alterValue(root.left);
root.val = node.val;
node = node.next;
alterValue(root.right);
}
}
编辑于 2018-08-05 15:15:11
回复(0)
同志们求优化，C++这么做会堆栈溢出，Java就不会
if(head==NULL)return NULL;if(head->next==NULL){TreeNode *r=new TreeNode(head->val);return r;}ListNode *root=head;ListNode *pre=NULL;ListNode *fast=head;while(fast!=NULL&&fast->next!=NULL){pre=root;root=root->next;fast=fast->next->next;}TreeNode *r=new TreeNode(root->val);pre->next==NULL;r->left=sortedListToBST(head);r->right=sortedListToBST(root->next);return r;
发表于 2017-09-08 22:51:46
回复(1)
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
if(head==NULL) return NULL;
ListNode *fast=head,*slow=head,*prev=NULL;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
prev=slow;
slow=slow->next;
}
TreeNode *root=new TreeNode(slow->val);
if(prev!=NULL){
prev->next=NULL;
root->left=sortedListToBST(head);
}
if(slow->next!=NULL){
root->right=sortedListToBST(slow->next);
}
return root;
}
};
发表于 2017-04-21 20:16:19
回复(2)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return TreeNode类
*/
public TreeNode sortedListToBST (ListNode head) {
// write code here
return buildTree(head,null);
}
public TreeNode buildTree(ListNode left, ListNode right){
if(left == right){
return null;
}
ListNode mid = getMedian(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(left, mid);
root.right = buildTree(mid.next, right);
return root;
}
public ListNode getMedian(ListNode left, ListNode right){
ListNode fast = left;
ListNode slow = left;
while(fast != right && fast.next != right){
fast = fast.next;
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
就经典的快慢指针，快指针速度是慢指针的2倍，然后慢指针到右边界，慢指针刚好到中间
发表于 2020-10-07 09:47:54
回复(0)
class Solution
{
public:
TreeNode *sortedListToBST(ListNode *head)
{
vector<int> v;
ListNode *p=head;
while(p)
v.push_back(p->val), p=p->next;
TreeNode *T=sortedArrayToBST(v,0,v.size()-1);
return T;
}
private:
TreeNode* sortedArrayToBST(const vector<int> &v,int left,int right)
{
if(left>right)
return NULL;
int mid=(left+right)/2;
mid=(right-left)&0x1?mid+1:mid;
TreeNode *node=new TreeNode(v[mid]);
TreeNode *nodeL=sortedArrayToBST(v,left,mid-1);
TreeNode *nodeR=sortedArrayToBST(v,mid+1,right);
node->left=nodeL, node->right=nodeR;
return node;
}
};
发表于 2017-10-08 11:30:47
回复(1)
import java.util.*;
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head==null)
return null;
ArrayList<Integer> list=new ArrayList<Integer>();
while(head!=null)
{
list.add(head.val);
head=head.next;
}
TreeNode root=find(list,0,list.size()-1);
return root;
}
public TreeNode find(ArrayList<Integer> list,int left,int right)
{
if(left>right)
return null;
int middle=0;
if((left+right)%2==0)
middle=(left+right)/2;
else
middle=(left+right)/2+1;
TreeNode node=new TreeNode(list.get(middle));
node.left=find(list,left,middle-1);
node.right=find(list,middle+1,right);
return node;
}
}
发表于 2017-08-23 10:52:10
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//在中点建立根节点,左边建左子树，右边建右子树
import java.util.ArrayList;
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head==null){
return null;
}
ArrayList<ListNode> list=new ArrayList<ListNode>();
while(head!=null){
list.add(head);
head=head.next;
}
int left=0;
int right=list.size()-1;
int mid=(left+right)/2;
if( (right-left)%2!=0){
mid=mid+1;
}
TreeNode node =new TreeNode(list.get(mid).val);
node.left=convert(list,left,mid-1);
node.right=convert(list,mid+1,right);
return node;
}
public TreeNode convert(ArrayList<ListNode> list,int left,int right){
if(right>list.size()-1 || left<0){
return null;
}
if(left>right){
return null;
}
int mid=(left+right)/2;
if( (right-left)%2!=0){
mid=mid+1;
}
TreeNode node =new TreeNode(list.get(mid).val);
node.left=convert(list,left,mid-1);
node.right=convert(list,mid+1,right);
return node;
}
}
发表于 2017-08-18 15:54:16
回复(0)
/*递归思路：1.f(p,end)找到链表（起始p,到终止end）中最中间的节点，作为根节点,并返回。2.这个节点的left=f(p,中间节点)3.这个节点的right=f(中间节点.next，end)*/publicclassSolution {publicTreeNode sortedListToBST(ListNode head) {return f(head,null);}publicTreeNode f(ListNode p,ListNode end){if(p==null||p==end)returnnull;if(p.next==end)returnnewTreeNode(p.val);ListNode slow=p;ListNode fast=p;while(fast.next!=end && fast.next.next!=end){slow=slow.next;fast=fast.next.next;}if(fast.next!=end)//边界值处理slow=slow.next;TreeNode root =newTreeNode(slow.val);root.left=f(p,slow);root.right=f(slow.next,end);returnroot;}}
发表于 2017-07-26 12:18:40
回复(0)
public TreeNode sortedListToBST(ListNode head) {
if(head==null)
return null;
ArrayList<Integer> list=new ArrayList<Integer>();
while(head!=null){
list.add(Integer.valueOf(head.val));
head=head.next;
}
return getBST(0,list.size()-1,list);
}
public TreeNode getBST(int low,int high,List list){
if(low<=high){
int mid=(low+high+1)/2;//mid取值注意，测试用例不是按常规mid取值的
TreeNode root=new TreeNode((int) list.get(mid));
root.left=getBST(low,mid-1,list);
root.right=getBST(mid+1,high,list);
return root;
}else
return null;
}
编辑于 2017-04-18 11:16:16
回复(2)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* 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==NULL) return NULL;
if(head->next==NULL) return new TreeNode(head->val);
ListNode *fast=head;
ListNode *low=head;
ListNode *pre=NULL;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
pre=low;
low=low->next;
}
TreeNode *root=new TreeNode(low->val);
pre->next=NULL;
root->left=sortedListToBST(head);
root->right=sortedListToBST(low->next);
pre->next=low; /*复原链表*/
return root;
}
};
发表于 2016-09-14 15:24:59
回复(3)
//递归构建平衡BST：折半查找思想，每次查找链表中间值插入，二叉树自然而然平衡
TreeNode *sortedListToBST(ListNode *head) {
if(head==NULL)
return NULL;
TreeNode *root=NULL;
insertNode(root,head);
return root;
}
void insertNode(TreeNode* &root,ListNode *head){
if(head==NULL)
return;
ListNode *p1=head,*p2=head,*p3,*p;
while(p2 && p2->next){
p3=p1;
p1=p1->next;
p2=p2->next->next;
}
TreeNode* node=new TreeNode(p1->val);
root=node;
if(p1!=head){
p3->next=NULL;
insertNode(root->left,head);
}
p=p1->next;
insertNode(root->right,p);
}
发表于 2016-09-01 16:38:08
回复(0)
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head==null)
return null;
if(head.next==null)
return new TreeNode(head.val);
ListNode rootNode = getRoot(head);
TreeNode root = new TreeNode(rootNode.val);
TreeNode right = sortedListToBST(rootNode.next);
rootNode.next = null;
TreeNode left = sortedListToBST(head);
root.left = left;
root.right = right;
return root;
}
private ListNode getRoot(ListNode head){
if(head==null||head.next==null)
return head;
ListNode fast = head;
ListNode root = head;
ListNode temp = null;
int count = 0;
while(fast!=null&&fast.next!=null){
temp = root;
root = root.next;
fast = fast.next.next;
count++;
}
//把下面的if注释去掉 通过
//if(count%2==0&&!(fast==null)){
//temp = root;
//root = root.next;
//}
temp.next = null;
return root;
}
}
结果不唯一
发表于 2016-05-31 20:22:07
回复(0)
public class Solution {public TreeNode sortedListToBST(ListNode head) {if(head==null)return null;if(head.next==null)return new TreeNode(head.val);ListNode fast=head;ListNode slow=head;ListNode leftRear=head;while(fast.next!=null&&fast.next.next!=null){fast=fast.next.next;leftRear=slow;slow=slow.next;}ListNode leftHead=null;if(slow!=head)leftHead=head;TreeNode root=new TreeNode(slow.val);ListNode rightHead=slow.next;leftRear.next=null;root.left=sortedListToBST(leftHead);root.right=sortedListToBST(rightHead);return root;}}
//找中间节点的判断条件写成fast!=null&&fast.next!=null,，当链表数量为偶数时，中间节点为第n/2+1个符合该题的测试思路，但事实上题设没说明，所以另一种情况上述答案也是正确的import java.util.*;public class Solution {public TreeNode sortedListToBST(ListNode head) {if(head==null)return null;ListNode slow = head;ListNode fast = head;ListNode temp = null;while(fast!=null&&fast.next!=null){fast = fast.next.next;temp = slow;slow = slow.next;}TreeNode root = new TreeNode(slow.val);if(temp!=null)temp.next = null;elsehead = null;root.left = sortedListToBST(head);root.right = sortedListToBST(slow.next);return root;}}
编辑于 2016-06-16 15:15:44
回复(0)
public TreeNode sortedListToBST (ListNode head) {
// write code here
if(head==null)
return null;
if(head.next==null)
return new TreeNode(head.val);
//中点
ListNode slow = head;
ListNode fast = head;
ListNode mid = slow;
while(fast!=null&&fast.next!=null){
mid = slow;
slow = slow.next;
fast = fast.next.next;
}
mid.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}
// write code here
if(head==null)
return null;
if(head.next==null)
return new TreeNode(head.val);
//中点
ListNode slow = head;
ListNode fast = head;
ListNode mid = slow;
while(fast!=null&&fast.next!=null){
mid = slow;
slow = slow.next;
fast = fast.next.next;
}
mid.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}
发表于 2022-01-05 18:11:55
回复(0)
险过的意思吗？？超过0.00%用Python 3提交的代码
class Solution: def sortedListToBST(self , head ): # 有序链表转二叉搜索树 # 需要找到链表的中点再递归划分左右子树 if not head: return None if not head.next: return TreeNode(head.val) # 找链表中点 cur, mid, nex = head, head, head while nex and nex.next: # 中点的前一个点 cur = mid mid = mid.next nex = nex.next.next # 左侧链表断开 cur.next = None # 递归构造树 root = TreeNode(mid.val) root.left = self.sortedListToBST(head) root.right = self.sortedListToBST(mid.next) # 返回树结点 return root
发表于 2021-09-06 11:07:20
回复(0)
找到中点很重要，然后递归。
import java.util.*;
public class Solution {
public TreeNode sortedListToBST (ListNode head) {
if(head==null){
return null;
}
ListNode p=head;
int count=0;
while(p!=null){
count++;
p=p.next;
}
int[] arr=new int[count];
p=head;
int i=0;
while(p!=null){
arr[i]=p.val;
i++;
p=p.next;
}
return build(arr,0,arr.length-1);
}
public TreeNode build(int[] num,int left,int right){
if(left>right){
return null;
}
if(left==right){
return new TreeNode(num[left]);
}
int mid=left+(right-left+1)/2;
TreeNode node=new TreeNode(num[mid]);
node.left=build(num,left,mid-1);
node.right=build(num,mid+1,right);
return node;
}
}
发表于 2020-11-05 19:30:00
回复(0)
问题信息
难度：
81条回答
111收藏
19302浏览
通过挑战的用户
查看代码-
2022-09-14 17:54:50 -
2022-09-14 15:27:13
-
2022-09-11 16:11:06 -
2022-09-02 11:12:37
-
2022-08-28 20:28:43
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
