子寒的博客
0%

leetcode109 Convert Sorted List to Binary Search Tree 解题报告

发表于 更新于 分类于

英文原题

Given the head of 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.

leetcode109

分析

    用递归的方法，把这个问题拆成多个子问题。题目给出的链表是排好序的，同时题目要求我们构建高度平衡二叉树，很容易想到取链表的中间点为根节点左边为左子树右边为右子树，接下来就是把左右子链表放入递归里面继续构建二叉树。     至于找中间点的方法是用快慢指针，慢指针一次走一步，快指针一次两步，等快指针到链表最后的时候慢指针就正好是链表中点了。

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return
        
        slow, fast = head, head
        before = ListNode(0, head)
        while fast and fast.next:
            before = before.next
            slow = slow.next
            fast = fast.next.next
        
        root = TreeNode(slow.val)
        before.next = None
        
        if slow.next:
            root.right = self.sortedListToBST(slow.next)
        if slow != head:
            root.left = self.sortedListToBST(head)
        
        return root