114. 二叉树开展为链表
题目起源：力扣（LeetCode）
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
题目
给定一个二叉树，原地将它开展为一个单链表。
例如，给定二叉树
1 / \ 2 5 / \ \3 4 6将其开展为：
1 \ 2 \ 3 \ 4 \ 5 \ 6解题思路
思路： 递归，非递归
递归
咱们先察看例子，能够发现，左子树开展成链表连贯在根节点，而右子树开展链表是紧跟在左子树开展的链表前面。这里应用递归的办法来解决。
应用后序遍历（递归）的具体做法：
- 先找到左子树的最右节点；
- 当找到左子树的最右节点时，令其指向根的右子树；
- 此时，再让根的右子树，指向根节点的左子树；
- 最初，令根节点的左子树为 None，循环直至右子树为空。
具体的代码见【代码实现 # 递归】
非递归
在后面咱们晓得，其实递归的思路，应用了额定的空间。这里，咱们应用非递归的办法来尝试解决。（具体做法同上）
具体的代码见【代码实现 # 非递归】
代码实现
# 递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ def unflod(node): if not node: return None unflod(node.left) unflod(node.right) # 后序遍历 if node.left: pre = node.left # 找到左子树的最右子节点，用以连贯根的右子树 while pre.right: pre = pre.right # 当找到左子树的最右子节点，令其指向根的右子树 pre.right = node.right # 而后令根的右子树指向根的左子树，令根的左子树为空 node.right = node.left node.left = None # 循环 node = node.right unflod(root)# 非递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ while root: if root.left: pre_node = root.left # 同样先找到左子树的最右节点 while pre_node.right: pre_node = pre_node.right # 最右节点指向根节点的右子树 pre_node.right = root.right # 根的右子树指向根的左子树，同时置空左子树 root.right = root.left root.left = None root = root.right实现后果
实现后果 | 递归
实现后果 | 非递归
欢送关注
公众号 【书所集录】