@[TOC]
题目
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表: [-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
解析
我感觉这个题目还是很有意思的,我们一般构建平衡二叉树的时候可能需要一个高度元素,但是这里很巧妙的给的链表是有序的。
解法一
采用递归的方式做这道题,理由是我们直到平衡二叉树本身就带有递归的性质,根节点的左右子树都是平衡二叉树,正是利用这个特性,我们将链表分为左链表,中间节点和右链表三段,对中间节点构建TreeNode root,
root.left= 递归(左链表头节点);
root.right = 递归(右链表的头节点)
直到参数节点为空或者下一个节点为空为止。
中间节点
那么这里如何找中间节点?
当然你可以用变量直接从头到尾的遍历一遍,然后除以2。当然也可以使用快慢指针,快指针一次跑两个节点,慢指针一次跑一个,当快指针到头的时候,慢指针就是中间的位置。如果是偶数个节点的话,中间两个都可以做根结点。最后我们切断中间节点和之前链表的联系(这里遍历的时候就需要记录慢指针的前驱节点)
整体的空间复杂度就是O(logn),因为使用了递归,时间复杂度(nlogn),怎么求时间复杂度:假设链表长为N,第一次N/2找到中点,继续N/4找二行中点,找了两个链表,第三行找了四个链表,想象成树总共有logN行。就可以写成下图中的公式。
这里为了方便理解我画了个图:
然后贴出自己的代码和运行截图,然后分享一个小插件,刷leetcode题可以用idea的一个插件,非常的方便,界面如末尾图,可以百度下怎么安装。
解法一代码
public TreeNode sortedListToBST(ListNode head) {
if (head == null){
return null;
}
if (head.next == null){
return new TreeNode(head.val);
}
//代表前一半链表的尾
ListNode pre = head;
//代表后一半链表的头
ListNode slow = head;
ListNode fast = head;
//寻找中间节点
while (fast != null && fast.next != null){
fast = fast.next;
fast = fast.next;
pre = slow;
slow = slow.next;
}
pre.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}
解法二
第二种解法和第一种解法类似,只不过这里采取以空间换时间,我们将链表中的节点值全部放到数组中,这样每一次在确定中间节点的时候就不需要遍历了。只需要,这样时间复杂度就是O(N)。
解法二代码
public TreeNode sortedListToBST(ListNode head){
//处理特殊情况
if (head == null){
return null;
}else if (head.next == null){
return new TreeNode(head.val);
}
ListNode cur = head;
int key = 0;
//我用hashmap代替int数组得了,不然还得统计长度,创建数组
HashMap<Integer,Integer> map = new HashMap<>();
while (cur!= null){
map.put(key++,cur.val);
cur = cur.next;
}
TreeNode root = sortedListToBST(0,map.size()-1,map);
return root;
}
//递归生成二叉树
private TreeNode sortedListToBST(int l, int r, HashMap<Integer, Integer> map) {
if (l>r){
return null;
}
int mid = (l+r)/2;
TreeNode root= new TreeNode(map.get(mid));
root.left = sortedListToBST(l,mid-1,map);
root.right = sortedListToBST(mid+1,r,map);
return root;
}
解法三
第三种方法和第二种稍微不同,这里采用二叉搜索树中序遍历的思想,链表的第一个节点肯定是二叉树最左边的节点了塞,依次是root,root.right。通过这种规律,我们先DFS构造做左边的,然后回溯构造root。
解法三代码
//第三种方法,二叉树的中序遍历
int index = 0;
public TreeNode sortedListToBST(ListNode head){
if (head == null){
return null;
}
if (head.next == null){
return new TreeNode(head.val);
}
ListNode cur = head;
//
HashMap<Integer,Integer> map = new HashMap<>();
int l=0;
while (cur != null){
map.put(l++,cur.val);
cur = cur.next;
}
TreeNode root = sortedListToBST(0,map.size()-1,map);
return root;
}
private TreeNode sortedListToBST(int l, int r, HashMap<Integer, Integer> map) {
if (l>r){
return null;
}
//这里的处理稍微有点点不同,我们知道链表的值是中序遍历的结果,所以我们就利用中序遍历这个条件
int mid = (l+r)/2;
//先找到最左边的节点,然后构造根,最后构造右节点,知道构造完成。
TreeNode left = sortedListToBST(l,mid-1,map);
TreeNode root = new TreeNode(map.get(index));
//第一个值读取过后,就轮到第二个
index++;
root.left = left;
root.right = sortedListToBST(mid+1,r,map);
return root;
}
插件
idea中的leetcode插件
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems