【leetcode】:109. 有序链表转换二叉搜索树

2021/8/27 6:07:30

本文主要是介绍【leetcode】:109. 有序链表转换二叉搜索树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目如下,这里做一个记录:

 

 思路:

1.首先使用快慢指针知道中点

2.然后使用递归得到avl平衡二叉树,因为中点作为root后,正好可以满足二叉搜索树的性质,也就是right node一定比left node更大,同时也可以满足avl平衡二叉树的性质,左右两边最多相差一个node。

# 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: ListNode) -> TreeNode:
        if not head:
            return None
        elif not head.next:
            return TreeNode(head.val)
        
        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        #这个pre在这里的作用是什么?
        #print(slow.val)
        #找到中点,只需要使用经典的快慢指针即可。同时为了防止环的出现, 我们需要斩断指向 mid 的 next 指针,因此需要记录一下中点前的一个节点,这只需要用一个变量 pre 记录即可。
        #因为pre和slow共有地址,因此pre.next=none,则slow.next=none too!
        root = TreeNode(slow.val)
        pre.next = None

        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

得解!

问题,本题目很经典,但是实在是不知道这个pre node的作用是什么?因为我即使不使用pre,直接断开slow到mid的指针,程序则会报错,太奇怪了。。。



这篇关于【leetcode】:109. 有序链表转换二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程