Leetcode109——Convert Sorted List to Binary Search Tree

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. 问题描述

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

2. 求解

这个题主要是根据一个有序链表构造二叉查找树(树的左结点小于根节点,根节点小于右结点,子树具有同样的性质)。与有序数组最大的不同在于有序链表只能从前往后遍历,不能像有序数组一样访问任意位置的元素。因此构造时需要按顺序构造,其实有序链表是二叉查找树的中序遍历。因此需要按照中序遍历的顺序进行构建,先构建左子树,再构造根节点,最后构造右子树。由于是链表,每次构造之后头结点应该进行移动,Java中用了一个静态变量来保存根节点的位置。构造方法主要是递归,每次构建子树时都需要将数组分成左右两半,左边的构建左子树,右边的构建右子树,中间元素构造根节点。

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
42
43
44
45
46
47
48
49
50
51
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
static ListNode h;
public TreeNode sortedListToBST(ListNode head) {
if(head == null) {
return null;
}
int length = 0;
h = head;
//得到链表长度
while(head != null) {
length++;
head = head.next;
}
return buildBinarySearchTree(h, 0, length - 1);
}
public TreeNode buildBinarySearchTree(ListNode head, int start, int end) {
if(start > end) {
return null;
}
int mid = (start + end) / 2;
//先构建左子树
TreeNode left = buildBinarySearchTree(h, start, mid - 1);
//再构造根节点
TreeNode root = new TreeNode(h.val);
h = h.next;
//最后构造右子树
TreeNode right = buildBinarySearchTree(h, mid + 1, end);
root.left = left;
root.right = right;
return root;
}
}
如果有收获,可以请我喝杯咖啡!