【剑指offer】36.二叉搜索树与双向链表

本题利用中序遍历&＃43;深度优先搜索解决。
参考&＃xff1a;https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/

根据上述思路&＃xff0c;代码如下&＃xff1a;

# Definition for a binary tree node.
# class Node:
# def __init__(self, val&＃61;0, left&＃61;None, right&＃61;None):
# self.val &＃61; val
# self.left &＃61; left
# self.right &＃61; rightclass Solution:# 深度优先搜索&＃xff0c;中序遍历二叉搜索树def dfs(self, cur):if not cur: # 当节点cur为空&＃xff0c;代表越过叶子节点&＃xff0c;直接返回return Noneself.dfs(cur.left) # 递归左子树# 构建链表if not self.pre: # 如果pre为空&＃xff0c;说明正在访问链表的头节点&＃xff0c;令head为curself.head &＃61; curelse: # 否则&＃xff0c;建立双向引用self.pre.right &＃61; curcur.left &＃61; self.preself.pre &＃61; cur # 更新preself.dfs(cur.right) # 递归右子树# 主函数def treeToDoublyList(self, root: &＃39;Node&＃39;) -> &＃39;Node&＃39;:# 特例&＃xff1a;如果root为空&＃xff0c;说明二叉搜索树为空&＃xff0c;则返回的链表亦为空if not root:return None# 定义空节点preself.pre &＃61; Noneself.dfs(root)# 链表的首尾相连self.head.left &＃61; self.preself.pre.right &＃61; self.headreturn self.head


时间复杂度分析

假设二叉搜索树有$N$个节点&＃xff0c;中序遍历需要遍历所有节点&＃xff0c;因此时间复杂度为$O(N)$。