首页 > 试题广场 >

有序链表变成二叉搜索树

[编程题]有序链表变成二叉搜索树
  • 热度指数：20418 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST）
示例1

输入

{-1,0,1,2}

输出

{1,0,2,-1}

说明：本题目包含复杂数据结构TreeNode、ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
牛客319355229号头像 牛客319355229号
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;
    }
发表于 2022-01-05 18:11:55 回复(0)
Java
金虹桥招财猫头像 金虹桥招财猫 
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)
Java
一个菜鸡的自我修养头像 一个菜鸡的自我修养 
//使用一个列表来保存链表中的数据
import java.util.*;
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        ArrayList<Integer> list=new ArrayList<>();
      if(head==null) return null;
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
      
        return sortedListToBST(list,0,list.size()-1);
    }
    private TreeNode sortedListToBST(ArrayList<Integer> list,int left,int right){
        if(left>right)
            return null;
        if(left==right)
            return new TreeNode(list.get(left));
        int mid=left+(right+1-left)/2;
        TreeNode root=new TreeNode(list.get(mid));
        root.left=sortedListToBST(list,left,mid-1);
         root.right=sortedListToBST(list,mid+1,right);
        return root;
    }
}

发表于 2018-04-02 16:23:12 回复(0)
Java
七仔0312头像 七仔0312 
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)
            return new TreeNode(head.val);
        ListNode slow = head, fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.next.val);
        root.right = sortedListToBST(slow.next.next);
        slow.next = null;
        root.left = sortedListToBST(head);
        return root;
    }
}
发表于 2018-03-17 19:38:01 回复(0)
Java
无名huster头像 无名huster 
//将一个有序链表转换为一个二叉搜索树，类似于有序数组转换为二叉搜索树
//找到链表的中值节点作为二叉搜索树的根节点，之后对左右两边的子链表再进行重复操作，即递归
//对于链表来说，找中间位置，可以使用一块一慢指针的方式来解决
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head != null){
            return getTree(head,null);
        }
        return null;
    }
    
    private TreeNode getTree(ListNode startNode ,ListNode endNode){
        //结束条件
        if(startNode == endNode){
            return null;
        }
        ListNode slowNode = startNode;
        ListNode fastNode = startNode;
        
        while(fastNode != endNode && fastNode.next != endNode){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        TreeNode treeNode = new TreeNode(slowNode.val);
        //左右两个子链表不可以包括中间节点
        treeNode.left = getTree(startNode,slowNode);
        treeNode.right = getTree(slowNode.next,endNode);
        
        return treeNode;
    }
}

发表于 2017-09-01 11:09:14 回复(0)
Java
阿拉要洗澡头像 阿拉要洗澡
/**
 * 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)
Java
pp11头像 pp11 
/**
 * 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; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        ListNode slowNode = head;
        ListNode fastNode = head;
        ListNode preMid = null;
        while (fastNode.next != null && fastNode.next.next != null) {
            preMid = slowNode;
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        ListNode mid = null;
        ListNode right = null;
        if (fastNode.next == null) {
            mid = slowNode;
        } else {
            preMid = slowNode;
            mid = slowNode.next;
        }
        right = mid.next;
        mid.next = null;
        
        TreeNode root = new TreeNode(mid.val);
        TreeNode leftTree = null;
        TreeNode rightTree = null;
        if (preMid != null) {
            preMid.next = null;
            leftTree = sortedListToBST(head);
        }
        if (right != null) {
            rightTree = sortedListToBST(right);
        }
        root.left = leftTree;
        root.right = rightTree;
        return root;
    }
}

发表于 2017-08-06 21:53:14 回复(0)
Java
Zfirsty头像 Zfirsty 



	/*递归思路：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)
Java
QY_Mars头像 QY_Mars 
/*
     * Given a singly linked list where elements are sorted in ascending order,
     * convert it to a height balanced BST.
     * 主要使用递归来进行构建二叉排序树BST
     * 使用快慢指针来实现，一个指针前进一个，一个指针前进两个，当找到中间的值后需要断开指针从而使得链表分为两部分
     * 递归使用
     */
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)
            return null;
        if(head.next == null) return new TreeNode(head.val);
        ListNode preMid = null;
        ListNode mid = head;
        ListNode end = head;
        while(end != null && end.next != null) {
            preMid = mid;
            mid = mid.next;
            end = end.next.next;
        }
        preMid.next = null; // 断开
        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }
发表于 2017-06-08 14:40:31 回复(0)
Java
sc111头像 sc111
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        int len = 0;
        ListNode node = head;
        while(node != null) {
            len++;
            node = node.next;
        }
        TreeNode result = helper(head,0,len-1);
        return result;
    }
    
    private TreeNode helper(ListNode node,int start,int end) {
        if(node == null || start > end) return null;
        if(node.next == null)
            return new TreeNode(node.val);
        
        ListNode temp = node;
        int mid = (start + end) / 2 + (start + end) % 2;
        for(int i=start;i<mid;i++) {
            temp = temp.next;
        }
        
        TreeNode newnode = new TreeNode(temp.val);
        newnode.left = helper(node,start,mid-1);
        newnode.right = helper(temp.next,mid+1,end);
        return newnode;
    }
}
发表于 2017-04-21 15:18:07 回复(0)
Java
C32头像 C32 
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)
Java
吉吉国王头像 吉吉国王
测试用例有点坑哈哈，偶数时取得是中间第二个，第一个过不去，大家注意就是了，然后就是每次取中间值作为树根。 

public static TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        //赋值给数组
        int len = getLen(head);
        int[] arr = new int[len];
        ListNode p = head;
        for (int i = 0; p != null; i++, p = p.next){
            arr[i] = p.val;
        }
        System.out.println(Arrays.toString(arr));
        TreeNode root = buildBST(arr);
        return root;
    }
    private static TreeNode buildBST(int[] arr) {
        if (arr == null || arr.length == 0) //输入错误
            return null;
        return buildBST(arr, 0, arr.length - 1);
    }
    private static TreeNode buildBST(int[] arr, int lo, int hi) {
        if (lo > hi)  //递归出口
            return null;
        //取中间值
        int mid = lo + (hi - lo) / 2;
        int val = arr[mid];
        TreeNode root = new TreeNode(val);  //根
        root.left = buildBST(arr, lo, mid - 1);
        root.right = buildBST(arr, mid + 1, hi);
        return root;
    }
    //计算链表长度
    private static int getLen(ListNode head) {
        int len = 0;
        ListNode p = head;
        while (p != null){
            len++;
            p = p.next;
        }
        return len;
    }

发表于 2017-04-12 10:24:43 回复(3)
Java
城市里的养猫者头像 城市里的养猫者 
public class Solution { public TreeNode sortedListToBST(ListNode head) { if(head==null) return null; return toBST(head,null);
} public TreeNode toBST(ListNode head, ListNode tail){
    ListNode slow = head;
    ListNode fast = head; if(head==tail) return null; while(fast!=tail&&fast.next!=tail){
        fast = fast.next.next;
        slow = slow.next;
    }
    TreeNode thead = new TreeNode(slow.val);
    thead.left = toBST(head,slow);
    thead.right = toBST(slow.next,tail); return thead;
}

发表于 2017-03-11 23:40:26 回复(0)
Java
詆調壹點头像 詆調壹點 
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)
提交观点

问题信息

链表 树
难度：
15条回答 20546浏览

热门推荐

通过挑战的用户

查看代码

相关试题

有序链表变成二叉搜索树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号