三个月算法进阶--day66
目录
排序链表
中序遍历
双向链表
pre.next = cur cur.prev = pre
循环链表
head.prev = tail tail.next = head
中序遍历打印/修改指针
def dfs(root):
if not root: return
dfs(root.left)
print(root.val)
dfs(root.right)
leetcode剑指offer第36题二叉搜索树与双向链表
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
def dfs(cur):
if not cur: return
dfs(cur.left) # 递归左子树
if self.pre: # 修改节点引用
self.pre.right, cur.left = cur, self.pre
else: # 记录头节点
self.head = cur
self.pre = cur # 保存 cur
dfs(cur.right) # 递归右子树
if not root: return
self.pre = None
dfs(root)
self.head.left, self.pre.right = self.pre, self.head
return self.head