LeetCode: 109. Convert Sorted List to Binary Search Tree

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

109. Convert Sorted List to Binary Search Tree

LeetCode - Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解题分析

这道题跟 108. Convert Sorted Array to Binary Search Tree 类似。可以转化成数组（或链表）进行求解。这属于空间换时间的解法。

另外一种解法，就是使用快慢指针，找到中间节点，然后再构造二叉树。

还有一种解法：利用分治+中序遍历，先逐步构建左树，然后构建根节点，最后构建右树。

参考资料

有序链表转换二叉搜索树 - 有序链表转换二叉搜索树 - 力扣（LeetCode）

 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
/**
 * Runtime: 1 ms, faster than 68.60% of Java online submissions for Convert Sorted List to Binary Search Tree.
 * Memory Usage: 41.1 MB, less than 5.26% of Java online submissions for Convert Sorted List to Binary Search Tree.
 */
public TreeNode sortedListToBST(ListNode head) {
    if (Objects.isNull(head)) {
        return null;
    }
    List<Integer> nums = new ArrayList<>();
    while (Objects.nonNull(head)) {
        nums.add(head.val);
        head = head.next;
    }
    return buildTree(nums, 0, nums.size());
}

private TreeNode buildTree(List<Integer> nums, int start, int end) {
    if (start > end || start >= nums.size()) {
        return null;
    }
    int mid = start + (end - start) / 2;
    TreeNode root = new TreeNode(nums.get(mid));
    root.left = buildTree(nums, start, mid - 1);
    root.right = buildTree(nums, mid + 1, end);
    return root;
}

 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
  /**
   * 使用递归，将其逐步分解成左树，根节点，右树三部分，然后将其组成一棵树即可。
   */
  public TreeNode sortedListToBST(ListNode head) {
    if (head == null) {
      return null;
    }
    // 这里偷懒了，也可以使用快慢指针将一个数组分解成两部分
    List<Integer> nums = new ArrayList<>();
    while (head != null) {
      nums.add(head.val);
      head = head.next;
    }
    return buildTree(nums, 0, nums.size() - 1);
  }

private TreeNode buildTree(List<Integer> nums, int left, int right) {
  if (left > right) {
    return null;
  }
  if (left == right) {
    return new TreeNode(nums.get(left));
  }
  int mid = left + (right - left) / 2;
  TreeNode root = new TreeNode(nums.get(mid));
  root.left = buildTree(nums, left, mid - 1);
  root.right = buildTree(nums, mid + 1, right);
  return root;
}

 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
32
33
34
35
36
37
38
39
40
41
ListNode globalHead = null;

/**
 * 分支+中序遍历
 *
 * 注：没想到这个的效率更高。有点不可思议。
 *
 * 参考： https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/solutions/378582/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/[109. 有序链表转换二叉搜索树 - 官方题解^]
 */
public TreeNode sortedListToBST(ListNode head) {
  if (head == null) {
    return null;
  }
  int length = getLength(head);
  globalHead = head;
  return buildTree(0, length - 1);
}

private TreeNode buildTree(int left, int right) {
  if (left > right) {
    return null;
  }
  int mid = left + (right - left) / 2;
  TreeNode root = new TreeNode();
  root.left = buildTree(left, mid - 1);
  root.val = globalHead.val;
  globalHead = globalHead.next;
  root.right = buildTree(mid + 1, right);
  return root;
}

private int getLength(ListNode head) {
  int result = 0;
  while (head != null) {
    result++;
    head = head.next;
  }
  return result;
}