[114][中等][DFS] 二叉树展开为链表

题目描述

114. 二叉树展开为链表

给定一个二叉树，原地将它展开为一个单链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解题思路

寻找前驱节点

空间复杂度$O(1)$.

如果一个节点的左子节点不为空, 则该节点的左子树中的最后一个节点被访问之后, 该节点的右子节点被访问.

• 左子树中最后一个被访问的节点是左子树中的最右边的节点, 是右子树根节点的前驱结点

• 当前树的根节点是左子树根节点的前驱结点

递归地将树展开, 然后将左右子树根节点与它们的前驱结点相连.

# 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 dfs(node):
            if node is None:
                return

            raw_left, raw_right = node.left, node.right
            left = dfs(raw_left)
            right = dfs(raw_right)
            if left is not None:
                node.right = raw_left
                node.left = None
                node = left
            if right is not None:
                node.right = raw_right
                node = right
            return node

        dfs(root)