给定一个单链表,其中的元素按升序排序,请将它转化成平衡二叉搜索树(BST)
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倍,然后慢指针到右边界,慢指针刚好到中间
//使用一个列表来保存链表中的数据 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; } }
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;
}
}
//将一个有序链表转换为一个二叉搜索树,类似于有序数组转换为二叉搜索树 //找到链表的中值节点作为二叉搜索树的根节点,之后对左右两边的子链表再进行重复操作,即递归 //对于链表来说,找中间位置,可以使用一块一慢指针的方式来解决 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; } }
/** * 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; } }
/*递归思路: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;}}
/*
* 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;
}
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; }
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; }
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; }
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; } }