给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
分治(未优化版)
class Solution {
private ListNode findMid(ListNode head, ListNode end) {
if (head == end || head.next == end || head.next.next == end) {
return head;
}
ListNode slow = head.next;
ListNode fast = head.next.next;
while (fast.next != end && fast.next.next != end) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private TreeNode solve(ListNode start, ListNode end) {
/**
* 空节点
*/
if (start == end) {
return null;
}
ListNode mid = findMid(start, end);
TreeNode root = new TreeNode(mid.val);
root.left = solve(start, mid);
root.right = solve(mid.next, end);
return root;
}
public TreeNode sortedListToBST(ListNode head) {
return solve(head, null);
}
}
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
", next=" + next +
'}';
}
}
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 {
private ListNode globalNode;
private int getLength(ListNode head) {
int cnt = 0;
while (head != null) {
cnt++;
head = head.next;
}
return cnt;
}
private TreeNode solve(int start, int end) {
/**
* 空节点
*/
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode root = new TreeNode();
root.left = solve(start, mid - 1);
root.val = globalNode.val;
globalNode = globalNode.next;
root.right = solve(mid + 1, end);
return root;
}
public TreeNode sortedListToBST(ListNode head) {
this.globalNode = head;
return solve(0, getLength(head) - 1);
}
}
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
", next=" + next +
'}';
}
}
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;
}
}