Problem

Given the root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

!https://assets.leetcode.com/uploads/2021/01/14/flaten.jpg

1
2
3
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

1
2
3
Input: root = []
Output: []

Example 3:

1
2
3
Input: root = [0]
Output: [0]

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • 100 <= Node.val <= 100

Follow up:

Can you flatten the tree in-place (with

1
O(1)

extra space)?

Solve

前幾次試錯直接對(,,・ω・,,)

想法沒錯後，直接DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 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: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root :
            return
        left = root.left
        right = root.right

        def findlast(node):
            if node.right:
                node = findlast(node.right)
            return node
        root.left = None #記得把左清空
        root.right = self.flatten(left)
        findlast(root).right = self.flatten(right)

        return root