《剑指Offer》刷题笔记——面试题36. 二叉搜索树与双向链表
难度：中等
一、题目描述：
class Solution:
def __init__(self):
self.head, self.pre = None, None
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root:
return None
# 二叉搜索树的中序遍历是递增的，因此把标准中序遍历中 改变每个父节点的左右指向即可
# head, pre, tail = None,None,None # 不是集合，要在def里引用的话得放在__init__(self)里
def inorder(node=root):
if node:
# 中序遍历，先left
inorder(node.left)
# 中序遍历，然后父节点
if not self.pre:
self.head = node #记录初始头节点
else:
self.pre.right, node.left = node, self.pre # 按顺序链接节点
self.pre = node
# 中序遍历，最后 right
inorder(node.right)
inorder()
self.head.left, self.pre.right = self.pre, self.head # 链接首位节点，跳出递归的pre是最后一个节点
return self.head
作者：lockonlxf
相关文章
Hea
2020-10-30
Coral
2020-12-26
Heather
2021-08-04
Aggie
2020-09-20
Kathy
2020-03-08
Serafina
2020-03-27
Veronica
2020-04-14
Maleah
2023-07-20
Orianna
2023-07-20
Cain
2023-07-20
Grizelda
2023-07-20
Jayne
2023-07-20
Fern
2023-07-20
Gita
2023-07-20
Dabria
2023-07-20
Rabia
2023-07-21
Linnea
2023-07-21
Jennifer
2023-07-21
Jayne
2023-07-21
Maleah
2023-07-21