题目描述

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

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

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

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

1
2
3
	0
-3	9
-10	 5

答案不唯一，只要满足平常二叉树的特性即可。

题目中给出的数组已经按升序排序，我们需要将其转换为平衡二叉树。

解题思路

由于是二叉平衡树，所以根节点应该为中间值，这样树两边的元素高度在正负1范围内。

对于根节点两侧，也是一个平衡二叉树，可以递归调用来进行构建。

但是由于给出的是链表，不方便取值，所以可以先转换为数组。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public TreeNode sortedListToBSTSelf(ListNode head) {
  //先将链表转化为数组，由于数组需要预先知道容量，所以使用了arraylist容器
  List<Integer> values = new ArrayList<Integer>();
  while (head != null) {
    values.add(head.val);
    head = head.next;
  }
  return help(values, 0, values.size() - 1);
}

private TreeNode help(List<Integer> list, int left, int right) {
  if (left > right) {
    return null;
  }
  //取中间值作为根节点
  int mid = left + (right - left) / 2;
  TreeNode node = new TreeNode(list.get(mid));
  //左侧节点，用数组的左边继续构建
  node.left = help(list, left, mid - 1);
  //右侧节点，用数组的右边继续构建
  node.right = help(list, mid + 1, right);
  return node;
}