文章作者：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中用了一个静态变量来保存根节点的位置。构造方法主要是递归，每次构建子树时都需要将数组分成左右两半，左边的构建左子树，右边的构建右子树，中间元素构造根节点。
/**
* 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;
}
}
