【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. 有序链表转换二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升