109. 有序链表转换二叉搜索树

题目：

109. 有序链表转换二叉搜索树

题解：

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("***************************************");
    }
}