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 = right
class 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 = right
class 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

实现后果

实现后果 | 递归

实现后果 | 非递归

欢送关注

公众号【书所集录】