《剑指Offer》刷题笔记——面试题36. 二叉搜索树与双向链表
版权申诉
167 浏览量
2020-12-22
09:32:29
上传
评论
收藏 119KB PDF 举报
《剑指《剑指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
评论0
最新资源