题目：
题解：
1. 题解一：
2. 题解二：
注：
代码：
1. 代码一：
/** * code109 */
import java.util.*;
public class code109 {
public static TreeNode sortedListToBST(ListNode head) {
// 1.遍历链表，使用数组保留节点升序值
if (head == null) {
return null;
}
List<Integer> values = new ArrayList<>();
while (head != null) {
values.add(head.val);
head = head.next;
}
// 2.递归构建二叉树，链表值为中序遍历结果
return sort(values, 0, values.size() - 1);
}
public static TreeNode sort(List<Integer> values, int start, int end) {
if (start > end) {
return null;
}
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(values.get(mid));
root.left = sort(values, start, mid - 1);
root.right = sort(values, mid + 1, end);
return root;
}
private static ListNode createLinkedList(int[] arr) {// 将输入的数组输入到链表中
if (arr.length == 0) {
return null;
}
ListNode head = new ListNode(arr[0]);
ListNode current = head;
for (int i = 1; i < arr.length; i++) {// 过程
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
private static void printLinkedList(ListNode head) {// 将链表结果打印
ListNode current = head;
while (current != null) {
System.out.printf("%d -> ", current.val);
current = current.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
int x[] = { -10, -3, 0, 5, 9 };
ListNode list = createLinkedList(x);
System.out.println("***************************************");
printLinkedList(list);
System.out.println("***************************************");
TreeNode tree = sortedListToBST(list);
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
2. 代码二：
/** * code109 */
import java.util.*;
public class code109 {
// 解法二：
public static TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
return sort(head, null);
}
public static TreeNode sort(ListNode head, ListNode tail) {
if (head == tail) {
return null;
}
// 初始化快慢指针
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
// 慢指针指向中点节点
TreeNode root = new TreeNode(slow.val);
root.left = sort(head, slow);
root.right = sort(slow.next, tail);
return root;
}
private static ListNode createLinkedList(int[] arr) {// 将输入的数组输入到链表中
if (arr.length == 0) {
return null;
}
ListNode head = new ListNode(arr[0]);
ListNode current = head;
for (int i = 1; i < arr.length; i++) {// 过程
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
private static void printLinkedList(ListNode head) {// 将链表结果打印
ListNode current = head;
while (current != null) {
System.out.printf("%d -> ", current.val);
current = current.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
int x[] = { -10, -3, 0, 5, 9 };
ListNode list = createLinkedList(x);
System.out.println("***************************************");
printLinkedList(list);
System.out.println("***************************************");
TreeNode tree = sortedListToBST(list);
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
京公网安备 11010502036488号