Flatten Binary Tree to Linked List LeetCode solution in Python

1
# Runtime: 59 ms (Top 52.37%) | Memory: 15.1 MB (Top 89.03%)
2
# Call the right of the tree node till the node root left and right is not None
3
# After reaching the bottom of the tree make the root.right = prev and
4
# root.left = None and then prev = None
5
# Initially prev will point to None but this is used to point the previously visited root node
6
# Prev pointer helps us to change the values from left to right
7
class Solution:
8
    def flatten(self, root: Optional[TreeNode]) -> None:
9
        """
10
        Do not return anything, modify root in-place instead.
11
        """
12
        prev = None  # You can also define that variable inside the init function using self keyword
13

14
        def dfs(root):
15
            nonlocal prev
16

17
            if not root:
18
                return
19

20
            dfs(root.right)
21
            dfs(root.left)
22

23
            root.right = prev
24
            root.left = None
25
            prev = root
26

27
        dfs(root)
28

29

30
# If the above solution is hard to understand than one can do level order traversal
31
# Using Stack DS but this will increase the space complexity to O(N).