难度: Easy
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。
注意：本题相对原题稍作改动
示例：
输入： [4,2,5,1,3,null,6,0] 输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示：
运行时间: 48 ms
内存: 22.9 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def convertBiNode(self, root: TreeNode) -> TreeNode:
self.pre = self.ans = None
def dfs(root):
if not root:
return
dfs(root.left)
root.left = None
if self.pre:
self.pre.right = root
if self.pre is None:
self.ans = root
self.pre = root
dfs(root.right)
dfs(root)
return self.ans
这个题解采用了深度优先搜索（DFS）的方法，特别是中序遍历，来实现二叉搜索树到单向链表的转换。中序遍历的顺序是左-根-右，这正好符合二叉搜索树的节点值从小到大的顺序。在遍历过程中，每访问一个节点，就将其左子节点设为空，并将其与前一个访问的节点（pre）的右子节点连接起来。如果是遍历到的第一个节点，则将其设置为链表的头节点。通过这种方式，可以在遍历结束时得到一个单向链表，链表中的节点顺序与二叉搜索树的中序遍历顺序相同。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def convertBiNode(self, root: TreeNode) -> TreeNode:
self.pre = self.ans = None # 初始化前一个节点和答案节点
def dfs(root):
if not root:
return # 如果当前节点为空，返回
dfs(root.left) # 先递归处理左子树
root.left = None # 将当前节点的左指针置空
if self.pre:
self.pre.right = root # 如果前一个节点存在，将前一个节点的右指针指向当前节点
if self.pre is None:
self.ans = root # 如果前一个节点不存在，说明当前节点是最小节点，设为头节点
self.pre = root # 更新前一个节点
dfs(root.right) # 递归处理右子树
dfs(root)
return self.ans # 返回转换后的链表的头节点
在将二叉搜索树转换为单向链表的过程中，将当前节点的左子节点设为空是为了断开原来的二叉树结构，使每个节点只保留向右的连接。这样做的目的是确保转换后的结构不再是二叉树，而是形成一个单向链表。在单向链表中，每个节点只有一个指向下一个节点的连接（即右子节点），而没有向左的连接。这样可以保持链表的单向性质，同时也保证了链表中元素的顺序与二叉搜索树的中序遍历顺序一致，即从小到大。
递归函数`dfs`通过以下步骤确保所有节点都正确连接成单向链表：1. 首先递归遍历左子树，这样可以确保按照中序遍历的顺序访问每个节点。2. 访问当前节点时，将其左子节点设为空，断开左侧的连接。3. 检查是否存在前一个访问的节点（`pre`），如果存在，则将前一个节点的右子节点指向当前节点，从而连接前一个节点与当前节点。4. 如果`pre`不存在，说明当前节点是遍历的第一个节点，将其设置为链表的头节点。5. 更新`pre`为当前节点，以便在后续的遍历中将其作为前一个节点使用。6. 最后递归遍历右子树。通过这种方式，每个节点在访问时都正确地连接到链表中，从而在遍历结束时形成一个完整的单向链表。
在二叉搜索树中的空节点在转换过程中不需要进行特殊处理。在递归函数`dfs`中，一旦遇到一个空节点，函数将直接返回并不执行任何操作。这意味着空节点不会对链表的构成产生任何影响，也不会被包括在最终的链表结构中。空节点的存在主要是作为递归遍历的终止条件，帮助函数在适当的时候停止递归，确保只有有效的非空节点被处理并加入到链表中。