题目描述
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
注意:
- 有序链表构建的高度平衡的二叉树就是平衡二叉树
- 简单容易想到的就是链表转为有序数组,直接构建,但是这样需要额外的空间。
- 要求空间O(1)的情况下可以使用双指针快慢指针,当快指针走到区间的尽头,满慢指针刚好走到 中间
解答
链表转有序集合,直接递归构建
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
while(head != null){
list.add(head.val);
head = head.next;
}
int len = list.size();
return buildBST(0,len-1);
}
public TreeNode buildBST(int start,int end){
if(start > end ){
return null;
}
int mid = (start + end) / 2;
TreeNode node = new TreeNode(list.get(mid));
node.left = buildBST(start,mid -1);
node.right = buildBST(mid + 1,end);
return node;
}
}
快慢指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
return helper(head,null);
}
private TreeNode helper(ListNode head,ListNode tail){
if(head == tail){
return null;
}
// 快慢指针
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 = helper(head,slow);
root.right = helper(slow.next,tail);
return root;
}
}