1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| # @Title: 二叉搜索树与双向链表 (二叉搜索树与双向链表 LCOF)
# @Author: 15816537946@163.com
# @Date: 2022-02-19 13:45:29
# @Runtime: 36 ms
# @Memory: 16 MB
"""
# 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(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
|