1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution:
 8     def flatten(self, root) -> None:
 9         def pre_dfs(root):
10             q = [root]
11             ans = []
12             while len(q):
13                 node = q[-1]
14                 q = q[:-1]
15                 ans.append(node.val)
16                 if node.right:
17                     q.append(node.right)
18                 if node.left:
19                     q.append(node.left)
20             print(ans)
21         
22         def last_dfs(root):
23             q = [root]
24             ans = []
25             pre = None
26             while len(q):
27                 node = q[-1]
28                 if (node.left is None and node.right is None) or (pre is not None and (pre == node.left or pre == node.right)):
29                     q = q[:-1]
30                     ans.append(node.val)
31                     pre = node
32                     # print(pre.val)
33                 else:
34                     if node.right:
35                         q.append(node.right)
36                     if node.left:
37                         q.append(node.left)
38                     
39             print(ans)
40 
41         def mid_dfs(root):
42             q = []
43             ans = []
44             node = root
45             while len(q) or node is not None :
46                 while node is not None:
47                     q.append(node)
48                     node = node.left
49                 
50                 # print ([it.val for it in q], node)
51                 if len(q):
52                     node = q[-1]
53                     ans.append(node.val)
54                     q = q[:-1]
55 
56                     node = node.right
57             print(ans)
58 
59         # pre_dfs(root)
60         # last_dfs(root)
61         mid_dfs(root)