题目4：
给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST）
思路：
1.该链表是有序的，根据平衡二叉搜索树的构成特点，在递归时每次把中间的值加入树的节点即可形成BST（平衡二叉搜索树的构成特点，递归）
2.找中间值,可以使用快慢指针，或者将链表复制到有序数组中即可找到（快慢指针，链表转数组）
3.注意试题认可的偶个数情况，中点是哪个，例如a,b,c,d（有的认为b是中点，有的认为c是中点）
代码：
方式一，不使用数组，使用快慢指针
/**
* 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 (null == head){
return null;
}
if (null == head.next){
return new TreeNode(head.val);
}
ListNode slow = head, fast = head.next.next;
while (fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
TreeNode node = new TreeNode(slow.next.val);
node.right = sortedListToBST(slow.next.next);
slow.next = null;
node.left = sortedListToBST(head);
return node;
}
}
方式二，使用数组，虽然时间复杂度都是O(logN)，空间复杂度都是O（N）,但使用数组复制肯定会销毁额外的空间,比起方式一弱一丢丢
/**
* 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 node = head;
int len = 0;
while(node != null) {
len ++;
node = node.next;
}
int[] nums = new int[len];
int k = 0;
while(head != null){
nums[k++] = head.val;
head = head.next;
}
return CreateTree(nums, 0, nums.length - 1);
}
public TreeNode CreateTree(int []nums, int start, int end){
if(start > end)
return null;
int mid = (start + end) /2;//这里是向下取整
if((start + end) %2!=0){
mid+=1;//看试题认可中点的方式，这里选择加一或者减一
}
TreeNode head = new TreeNode(nums[mid]);
head.left = CreateTree(nums, start, mid- 1);
head.right = CreateTree(nums, mid+ 1, end);
return head;
}
}
网友评论