[LeetCode] 109. Convert Sorted List to Binary Search Tree 把

发布时间：2020-12-14 03:46:06 所属栏目：大数据来源：网络整理

导读：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

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,5,9],One possible answer is: [0,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,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 把有序数组转成二叉搜索树

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!