p109

发表于 | 分类于 |

LeetCode p109 Convert Sorted List to Binary Search Tree 题解

1.题目：

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

题意：

输入一个递增的链表，输出它的平衡二叉树。

2.解题思路:

快慢指针找中间，递归。

3.代码

[title] [] [url] [link text]
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
 
/**
 * 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 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
			return null;
		return ToBst(head, null);
	}

	public TreeNode ToBst(ListNode head, ListNode tail) {
		if (head == tail)
			return null;
		ListNode fast = head;
		ListNode slow = head;

		while (fast.next != tail && fast.next.next != tail) {
			fast = fast.next.next;
			slow = slow.next;
		}
		TreeNode node = new TreeNode(slow.val);
		node.left = ToBst(head, slow);
		node.right = ToBst(slow.next, tail);
		return node;
	}
}

4.一些总结：