共计 1532 个字符,预计需要花费 4 分钟才能阅读完成。
题目
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表:[-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
题解
这道题和上一道类似, 改动是把数组改成了链表。链表求中间节点的经典方法是快慢指针, 慢指针每次走一步, 快指针每次都走两步,这样快指针走到链表结尾的时候,慢指针就指向中间节点。这样就可以把问题转化为递归的子问题进行求解。
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
return helper(head, null);
}
public TreeNode helper(ListNode head, ListNode tail) {
if (head == null || head == tail) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != tail && fast.next.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode current = new TreeNode(slow.val);
current.left = helper(head, slow);
current.right = helper(slow.next, tail);
return current;
}
}
这道题目还有一个比较巧妙的办法是利用 BST 中序遍历是升序的性质,去求解,具体看代码注释。
class Solution {
private ListNode node;
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
int size = 0;
ListNode runner = head;
node = head;
while (runner != null) {
runner = runner.next;
size++;
}
// 先计算有几个节点
return inorderHelper(0, size – 1);
}
public TreeNode inorderHelper(int start, int end) {
if (start > end) {
return null;
}
// 划分左右子树
int mid = start + (end – start) / 2;
TreeNode left = inorderHelper(start, mid – 1);
// 中序遍历
TreeNode treenode = new TreeNode(node.val);
treenode.left = left;
node = node.next;
TreeNode right = inorderHelper(mid + 1, end);
treenode.right = right;
return treenode;
}
}
最关键的一个步骤是 node = node.next 这步的意思是基于:在 BST 中任意子树,它的中序遍历的结果如果存在一个链表中,一定是一个升序的,可以一一对应上,所以中序遍历完(这里是构建完)一个节点链表 +1。
热门阅读
【Leetcode】108. 将有序数组转换为二叉搜索树
【Leetcode】107. 二叉树的层次遍历 II
【Leetcode】105. 从前序与中序遍历序列构造二叉树
【Leetcode】106. 从中序与后序遍历序列构造二叉树
手撕代码 QQ 群:805423079,群密码:1024