小黑昨晚又内耗了起床来个leetcode:109. 有序链表转换二叉搜索树

小黑做法:分治法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        self.arr = []
        # 遍历数组
        while head:
            self.arr.append(TreeNode(val=head.val))
            head = head.next
        # 分治函数
        def min_sort(list_):
            if list_:
            	# 寻找中间结点
                mid_node = list_[len(list_)//2]
                # 左结点
                left_mid = min_sort(list_[:len(list_)//2])
                # 右结点
                right_mid = min_sort(list_[len(list_)//2+1:])
                if left_mid:
                    mid_node.left = left_mid
                if right_mid:
                    mid_node.right = right_mid
                return mid_node
            return None
        return min_sort(self.arr)     
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

分治法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        def get_Medain(left,right):
            fast = left
            slow = left
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow
        
        def build_tree(left,right):
            if left == right:
                return None
            mid_node = get_Medain(left,right)
            # 转化为树结点
            mid_tree_node = TreeNode(val = mid_node.val)
            left_node = build_tree(left,mid_node)
            right_node = build_tree(mid_node.next,right)
            mid_tree_node.left = left_node
            mid_tree_node.right = right_node
            return mid_tree_node
        return build_tree(head,None)
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

中序+分治

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        def get_length(head):
            rel = 0
            while head:
                rel += 1
                head = head.next
            return rel
        self.dis_node = head
        def mid_dis(left,right):
            if left <= right:
                mid = (left + right) // 2
                left_node = mid_dis(left,mid-1)
                mid_node = TreeNode(val = self.dis_node.val)
                self.dis_node = self.dis_node.next
                right_node = mid_dis(mid+1,right)
                mid_node.left = left_node
                mid_node.right = right_node

                return mid_node
        length = get_length(head)
        return mid_dis(0,length-1)
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

小黑生活