首页 > itarticle > p109

p109

admin 11月 12, 2020 0

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]

 

 * 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  {
    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.一些总结：