LeetCode109-有序链表转换二叉搜索树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

中文链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

题目详述

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

题目详解

本题与 LeetCode108-将有序数组转换为二叉搜索树 的思路是一致的。不过数组支持随机存取，链表不支持随机存取，重点在于怎么恰当地从链表中得到中间结点。

  • 数组可以采用 lo + (hi - lo) / 2 的方式得到得到中间结点。
  • 链表得到中间结点的常规方法可以先遍历得到长度，再走一半距离。
  • 链表得到中间结点的更好的方法可以采用快慢指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class LeetCode_00109 {

    public TreeNode sortedListToBST(ListNode head) {
        return sortedListToBST(head, null);
    }

    /**
     * 每次找中间结点来构建二叉树，这样可以保证构建得到的二叉搜索树一定是平衡的二叉搜索树。
     * 可以利用快慢指针来找中间结点，注意链表结点总数奇偶性的差异（对本题没有影响）。
     * 为偶数时，fast 指针不能再前进时，fast 指向 null，slow 指向下中位数的结点。
     * 为奇数时，fast 指针不能再前进时，fast 指向尾结点，slow 指向中心结点。
     * @param head  头结点
     * @param end   尾结点的下一个结点
     * @return      二叉树的根结点
     */
    private TreeNode sortedListToBST(ListNode head, ListNode end) {
        if (head == end) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != end && fast.next != end) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head, slow);
        root.right = sortedListToBST(slow.next, end);
        return root;
    }
}