原题地址:
https://oj.leetcode.com/problems/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.
方法:
单纯。如何安排插入顺序,使得一棵二叉排序树接*衡?
你从中间开始插嘛。这样左子树和右子树之差或者为0,或者为1。
所以,这个问题的本质是找链表的中间节点。
找到中间节点后,递归产生左子树和右子树,在找左边子链表的中间节点和右边子链表的中间节点即可。
当然啦,最后返回中间节点。
全部代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
int len = countLen(head);
if (len == 0)
return null;
return constructTree(head,len); // len is the number of nodes in list.
} private TreeNode constructTree(ListNode head,int len)
{
if (head == null || len <= 0)
return null;
int mid = len / 2 + 1;
TreeNode tmp = new TreeNode(head.val);
tmp.left = null;
tmp.right = null;
if (mid == 0)
return tmp;
ListNode tar = findMidNode(head,mid);
tmp.val = tar.val;
tmp.left = constructTree(head,mid - 1);
tmp.right = constructTree(tar.next,len - mid);
return tmp;
} private ListNode findMidNode(ListNode head,int mid)
{
int count = 1;
while (mid != count++)
head = head.next;
return head;
} private int countLen(ListNode head)
{
int len = 0;
while (head != null)
{
len ++;
head = head.next;
}
return len;
}
}