python-leetcode 45.二叉树转换为链表

题目：

给定二叉树的根节点root,请将它展开为一个单链表：

展开后的单链表应该使用同样的TreeNode,其中right子指针指向链表中的下一个节点，而左子指针始终为空

展开后的单链表应该与二叉树先序遍历顺序相同

---

方法一：二叉树的前序遍历 

将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构，因此在前序遍历结束之后更新每个节点的左右子节点的信息，将二叉树展开为单链表。

通过递归实现前序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""preorderList=[]#创建一个空列表,用于存储二叉树的所有节点def preorderTraversal(root):#递归函数，用于对树进行前序遍历if root: #前序遍历的顺序是：根 -> 左 -> 右。preorderList.append(root)preorderTraversal(root.left)preorderTraversal(root.right)preorderTraversal(root)size=len(preorderList)#二叉树的节点总数for i in range(1,size): #从第二个节点开始，直到最后一个节点。因为链表的第一个节点已经由根节点 root 来表示prev,curr=preorderList[i-1],preorderList[i]#取当前节点 curr 和前一个节点 prevprev.left=None#将 prev 节点的左指针设置为 Noneprev.right=curr #将 prev 节点的右指针指向 curr

通过迭代的方式实现前序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""preorderList = []  # 初始化一个空列表用于存储二叉树的节点stack = []  # 初始化一个空栈用于存储遍历过程中暂时访问的节点node = root# 前序遍历二叉树while node or stack:while node:preorderList.append(node)  # 将当前节点添加到列表中stack.append(node)  # 将当前节点添加到栈中node = node.left  # 继续遍历左子树node = stack.pop()  # 当左子树遍历结束时，从栈中弹出一个节点，这个节点是待访问的右子节点（即上一个节点的右子树）node = node.right  # 继续访问右子树# 构建链表（右子树按前序遍历顺序连接）size = len(preorderList)for i in range(1, size):  # 从第二个节点开始（因为第一个节点已经是链表的头节点）prev, curr = preorderList[i - 1], preorderList[i]prev.left = None  # 清空左子树prev.right = curr  # 将前一个节点的右指针指向当前节点

时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。

空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n

---

方法三：寻找前驱节点

前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空，则该节点不需要进行展开操作。。如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。因此，问题转化成寻找当前节点的前驱节点。

对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点,，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""curr=rootwhile curr:if curr.left:predecessor=nxt=curr.left#用来找到左子树中最右的节点while predecessor.right:#找到左子树中的最右节点predecessor=predecessor.right #向右移动，寻找最右边的节点predecessor.right=curr.right#找到左子树中的最右节点后,将当前节点的右子树连接到左子树的最右节点上curr.left=None     #当前节点的左子树被置为curr.right=nxt#将当前节点的右指针指向左子树的根节点curr=curr.right #使curr移动到下一个节点（即当前右子树的第一个节点），继续遍历   

时间复杂度：O(n)其中 n 是二叉树的节点数。展开为单链表的过程中，需要对每个节点访问一次，在寻找前驱节点的过程中，每个节点最多被额外访问一次

空间复杂度：O(1)

源自力扣官方题解