(python version) 劍指offer 36. 二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 來源：力扣（LeetCode）

解题思路

递归遍历方法：从最小单元开始，深度优先搜索。

中序搜索：左节点右 => 补左指向节点 & 补右指向节点新增指针：记录遍历当前节点的前一个指针; 以及判定头指针深度优先算法：先往最左边最深搜索 => 中间节点 => 最右边搜索，因此最后一个 self.prev 指針为最后一个节点

头尾相连：将 self.head 与 self.prev 进行头尾相连双向指针

# 扩展至递归 # 最后头尾相连 # 中序遍历：补左子节点的右指针; 补右子节点的左指针 # 最后要头尾相连

Python 代码

""" # Definition for a Node. class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right """ class Solution: def treeToDoublyList(self, root: 'Node') -> 'Node': # 从最小单元的遍历 def dfs(root): if not root: return dfs(root.left) if self.pre: self.pre.right = root root.left = self.pre # 初始值设置头节点 else: self.head = root self.pre = root dfs(root.right) # main if not root: return None self.pre = None dfs(root) # 最后头尾相连 self.head.left = self.pre self.pre.right = self.head return self.head