标签: 栈 树 深度优先搜索 二叉搜索树 链表 二叉树 双向链表
难度: Medium
Submission
运行时间: 25 ms
内存: 16.6 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: 'Optional[Node]') -> 'Optional[Node]':
def dfs(cur):
if cur is None: return None
dfs(cur.left)
if self.pre is None:
self.head = cur
else:
self.pre.right, cur.left = cur, self.pre
self.pre = cur
dfs(cur.right)
if root is None: return None
self.pre = None
dfs(root)
self.head.left, self.pre.right = self.pre, self.head
return self.head
Explain
该题解使用了中序遍历的思路来将二叉搜索树转化为排序的双向链表。具体步骤如下： 1. 定义一个 dfs 函数，用于递归地进行中序遍历。 2. 在中序遍历的过程中，记录前一个访问的节点 pre。 3. 如果 pre 为 None，说明当前节点是第一个节点，将其设为双向链表的头节点 head。 4. 否则，将 pre 的右指针指向当前节点，当前节点的左指针指向 pre。 5. 更新 pre 为当前节点，继续遍历右子树。 6. 遍历完整棵树后，将头节点的左指针指向最后一个节点，最后一个节点的右指针指向头节点，形成循环双向链表。 7. 返回双向链表的头节点 head。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
def dfs(cur):
if cur is None: return None
# 递归遍历左子树
dfs(cur.left)
if self.pre is None:
# 如果 pre 为 None，说明当前节点是第一个节点，将其设为双向链表的头节点
self.head = cur
else:
# 否则，将 pre 的右指针指向当前节点，当前节点的左指针指向 pre
self.pre.right, cur.left = cur, self.pre
# 更新 pre 为当前节点
self.pre = cur
# 递归遍历右子树
dfs(cur.right)
if root is None: return None
self.pre = None
dfs(root)
# 将头节点的左指针指向最后一个节点，最后一个节点的右指针指向头节点，形成循环双向链表
self.head.left, self.pre.right = self.pre, self.head
return self.head
Explore
在递归遍历二叉搜索树构建双向链表时，当遇到空节点（即递归到叶子节点的左子节点或右子节点时），我们直接返回而不进行任何操作。这是因为空节点在构建链表时不占据任何位置，而只是表示树的边界。通过直接返回，我们避免了对空指针的错误引用，并确保了只有有效的树节点被添加到链表中，维护了链表的正确性。
选择在遍历过程中动态更新链表的连接而不是先存储所有节点的原因主要在于效率和空间的优化。动态更新链表的连接可以边遍历边构建链表，这样可以省去存储所有节点所需的额外空间，并且可以在遍历完即完成链表的构建，避免了后续还需遍历一次列表来构建链表的时间开销。此外，这种方法也更符合在递归过程中直接处理数据的编程范式。
题解中选择将头节点的左指针和最后一个节点的右指针相连接，形成循环双向链表的目的是为了提供无缝访问链表的头部和尾部。这在某些应用场景中（如需要循环遍历数据）非常有用。然而，如果不需要循环遍历数据，完全可以省略这一步骤，构建一个普通的双向链表。这取决于具体的应用需求。
为确保链表的双向连接性正确无误，应仔细处理每个节点的左右指针。在递归的每一步，当当前节点与前一个节点连接时，不仅需要设置当前节点的左指针指向前一个节点，还需设置前一个节点的右指针指向当前节点。这种双向连接确保了从任一节点都可以正确地向前或向后遍历。为防止错误，还应在函数开始时初始化头节点和前一个节点的指针，并在递归结束后检查头节点和尾节点的连接是否符合预期，特别是在形成循环链表的情况下。