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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0

     / \

   -3   9

   /   /

 -10  5

和 108. Convert Sorted Array to Binary Search Tree 思路一样，只不过一个是数组，一个是链表。数组可以通过index直接访问元素找到中点，而链表的查找中间点要通过快慢指针来操作。

Java:

class Solution {

    public TreeNode sortedListToBST(ListNode head) {

        if(head==null) return null;

        return toBST(head,null);

    }

    public TreeNode toBST(ListNode head, ListNode tail){

        ListNode slow = head;

        ListNode fast = head;

        if(head==tail) return null;

        while(fast!=tail&&fast.next!=tail){

            fast = fast.next.next;

            slow = slow.next;

        }

        TreeNode thead = new TreeNode(slow.val);

        thead.left = toBST(head,slow);

        thead.right = toBST(slow.next,tail);

        return thead;

    }

}

Python:

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

class Solution:

    head = None

    # @param head, a list node

    # @return a tree node

    def sortedListToBST(self, head):

        current, length = head, 0

        while current is not None:

            current, length = current.next, length + 1

        self.head = head

        return self.sortedListToBSTRecu(0, length)

    def sortedListToBSTRecu(self, start, end):

        if start == end:

            return None

        mid = start + (end - start) / 2

        left = self.sortedListToBSTRecu(start, mid)

        current = TreeNode(self.head.val)

        current.left = left

        self.head = self.head.next

        current.right = self.sortedListToBSTRecu(mid + 1, end)

        return current

Python:

def sortedListToBST(self, head):

    if not head:

        return

    if not head.next:

        return TreeNode(head.val)

    slow, fast = head, head.next.next

    while fast and fast.next:

        fast = fast.next.next

        slow = slow.next

    tmp = slow.next

    slow.next = None

    root = TreeNode(tmp.val)

    root.left = self.sortedListToBST(head)

    root.right = self.sortedListToBST(tmp.next)

    return root

C++:

class Solution {

public:

    TreeNode* sortedListToBST(ListNode* head) {

        auto curr = head;

        int n = 0;

        while (curr) {

            curr = curr->next;

            ++n;

        }

        return BuildBSTFromSortedDoublyListHelper(&head, 0, n);

    }

    TreeNode * BuildBSTFromSortedDoublyListHelper(ListNode **head, int s, int e) {

        if (s == e) {

            return nullptr;

        }

        int m = s + ((e - s) / 2);

        auto left = BuildBSTFromSortedDoublyListHelper(head, s, m);

        auto curr = new TreeNode((*head)->val);

        *head = (*head)->next;

        curr->left = left;

        curr->right = BuildBSTFromSortedDoublyListHelper(head, m + 1, e);

        return curr;

    }

};

类似题目：

[LeetCode] 108. Convert Sorted Array to Binary Search Tree 把有序数组转成二叉搜索树

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 109. Convert Sorted List to Binary Search Tree 把有序链表转成二叉搜索树

All LeetCode Questions List 题目汇总

最新文章

热门文章