1 # Definition for a binary tree node.
  2 # class TreeNode:
  3 #     def __init__(self, x):
  4 #         self.val = x
  5 #         self.left = None
  6 #         self.right = None
  7 
  8 
  9 
 10 # 递归
 11 # 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
 12 # 空间复杂度：空间复杂度：O(h)，h为树的高度。最坏情况下需要空间O(n)，平均情况为O(logn)
 13 
 14 # 递归1：二叉树遍历最易理解和实现版本
 15 class Solution:
 16     def preorderTraversal(self, root: TreeNode) -> List[int]:
 17         if not root:
 18             return []
 19         # 前序递归
 20         return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
 21         # # 中序递归 
 22         # return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
 23         # # 后序递归
 24         # return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
 25 
 26 # 递归2：通用模板，可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值
 27 class Solution:
 28     def preorderTraversal(self, root: TreeNode) -> List[int]:
 29         def dfs(cur):
 30             if not cur:
 31                 return      
 32             # 前序递归
 33             res.append(cur.val)
 34             dfs(cur.left)
 35             dfs(cur.right) 
 36             # # 中序递归
 37             # dfs(cur.left)
 38             # res.append(cur.val)
 39             # dfs(cur.right)
 40             # # 后序递归
 41             # dfs(cur.left)
 42             # dfs(cur.right)
 43             # res.append(cur.val)      
 44         res = []
 45         dfs(root)
 46         return res
 47 
 48 
 49 
 50 # 迭代
 51 # 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
 52 # 空间复杂度：O(h)，h为树的高度。取决于树的结构，最坏情况存储整棵树，即O(n)
 53 
 54 # 迭代1：前序遍历最常用模板（后序同样可以用）
 55 class Solution:
 56     def preorderTraversal(self, root: TreeNode) -> List[int]:
 57         if not root:
 58             return []        
 59         res = []
 60         stack = [root]
 61         # # 前序迭代模板：最常用的二叉树DFS迭代遍历模板
 62         while stack:
 63             cur = stack.pop()
 64             res.append(cur.val)
 65             if cur.right:
 66                 stack.append(cur.right)
 67             if cur.left:
 68                 stack.append(cur.left)
 69         return res
 70         
 71         # # 后序迭代，相同模板：将前序迭代进栈顺序稍作修改，最后得到的结果反转
 72         # while stack:
 73         #     cur = stack.pop()
 74         #     if cur.left:
 75         #         stack.append(cur.left)
 76         #     if cur.right:
 77         #         stack.append(cur.right)
 78         #     res.append(cur.val)
 79         # return res[::-1]
 80 
 81 # 迭代1：层序遍历最常用模板
 82 class Solution:
 83     def levelOrder(self, root: TreeNode) -> List[List[int]]:
 84         if not root:
 85             return []
 86         cur, res = [root], []
 87         while cur:
 88             lay, layval = [], []
 89             for node in cur:
 90                 layval.append(node.val)
 91                 if node.left: lay.append(node.left)
 92                 if node.right: lay.append(node.right)
 93             cur = lay
 94             res.append(layval)
 95         return res
 96 
 97         
 98         
 99 # 迭代2：前、中、后序遍历通用模板（只需一个栈的空间）
100 class Solution:
101     def inorderTraversal(self, root: TreeNode) -> List[int]: 
102         res = []
103         stack = []
104         cur = root
105         # 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
106         while stack or cur:
107             while cur:
108                 stack.append(cur)
109                 cur = cur.left
110             cur = stack.pop()
111             res.append(cur.val)
112             cur = cur.right
113         return res
114         
115         # # 前序，相同模板
116         # while stack or cur:
117         #     while cur:
118         #         res.append(cur.val)
119         #         stack.append(cur)
120         #         cur = cur.left
121         #     cur = stack.pop()
122         #     cur = cur.right
123         # return res
124         
125         # # 后序，相同模板
126         # while stack or cur:
127         #     while cur:
128         #         res.append(cur.val)
129         #         stack.append(cur)
130         #         cur = cur.right
131         #     cur = stack.pop()
132         #     cur = cur.left
133         # return res[::-1]
134         
135 
136 
137 # 迭代3：标记法迭代（需要双倍的空间来存储访问状态）：
138 # 前、中、后、层序通用模板，只需改变进栈顺序或即可实现前后中序遍历，
139 # 而层序遍历则使用队列先进先出。0表示当前未访问，1表示已访问。
140 class Solution:
141     def preorderTraversal(self, root: TreeNode) -> List[int]:
142         res = []
143         stack = [(0, root)]
144         while stack:
145             flag, cur = stack.pop()
146             if not cur: continue
147             if flag == 0:
148                 # 前序，标记法
149                 stack.append((0, cur.right))
150                 stack.append((0, cur.left))
151                 stack.append((1, cur))
152                 
153                 # # 后序，标记法
154                 # stack.append((1, cur))
155                 # stack.append((0, cur.right))
156                 # stack.append((0, cur.left))
157                 
158                 # # 中序，标记法
159                 # stack.append((0, cur.right))
160                 # stack.append((1, cur))
161                 # stack.append((0, cur.left))  
162             else:
163                 res.append(cur.val)  
164         return res
165         
166         # # 层序，标记法
167         # res = []
168         # queue = [(0, root)]
169         # while queue:
170         #     flag, cur = queue.pop(0)  # 注意是队列，先进先出
171         #     if not cur: continue
172         #     if flag == 0:
173                   # 层序遍历这三个的顺序无所谓，因为是队列，只弹出队首元素
174         #         queue.append((1, cur))
175         #         queue.append((0, cur.left))
176         #         queue.append((0, cur.right))
177         #     else:
178         #         res.append(cur.val)
179         # return res
180 
181 
182 
183 # 莫里斯遍历
184 # 时间复杂度：O(n)，n为节点数，看似超过O(n)，有的节点可能要访问两次，实际分析还是O(n)，具体参考大佬博客的分析。
185 # 空间复杂度：O(1)，如果在遍历过程中就输出节点值，则只需常数空间就能得到中序遍历结果，空间只需两个指针。
186 # 如果将结果储存最后输出，则空间复杂度还是O(n)。
187 
188 # PS：莫里斯遍历实际上是在原有二叉树的结构基础上，构造了线索二叉树，
189 # 线索二叉树定义为：原本为空的右子节点指向了中序遍历顺序之后的那个节点，把所有原本为空的左子节点都指向了中序遍历之前的那个节点
190 # emmmm，好像大学教材学过，还考过
191 
192 # 此处只给出中序遍历，前序遍历只需修改输出顺序即可
193 # 而后序遍历，由于遍历是从根开始的，而线索二叉树是将为空的左右子节点连接到相应的顺序上，使其能够按照相应准则输出
194 # 但是后序遍历的根节点却已经没有额外的空间来标记自己下一个应该访问的节点，
195 # 所以这里需要建立一个临时节点dump，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
196 # 具体参考大佬博客
197 
198 # 莫里斯遍历，借助线索二叉树中序遍历（附前序遍历）
199 class Solution:
200     def inorderTraversal(self, root: TreeNode) -> List[int]:
201         res = []
202         # cur = pre = TreeNode(None)
203         cur = root
204 
205         while cur:
206             if not cur.left:
207                 res.append(cur.val)
208                 # print(cur.val)
209                 cur = cur.right
210             else:
211                 pre = cur.left
212                 while pre.right and pre.right != cur:
213                     pre = pre.right
214                 if not pre.right:
215                     # print(cur.val) 这里是前序遍历的代码，前序与中序的唯一差别，只是输出顺序不同
216                     pre.right = cur
217                     cur = cur.left
218                 else:
219                     pre.right = None
220                     res.append(cur.val)
221                     # print(cur.val)
222                     cur = cur.right
223         return res
224 
225 
226 
227 # N叉树遍历
228 # 时间复杂度：时间复杂度：O(M)，其中 M 是 N 叉树中的节点个数。每个节点只会入栈和出栈各一次。
229 # 空间复杂度：O(M)。在最坏的情况下，这棵 N 叉树只有 2 层，所有第 2 层的节点都是根节点的孩子。
230 # 将根节点推出栈后，需要将这些节点都放入栈，共有 M?1个节点，因此栈的大小为 O(M)。
231 
232 
233 """
234 # Definition for a Node.
235 class Node:
236     def __init__(self, val=None, children=None):
237         self.val = val
238         self.children = children
239 """
240 
241 # N叉树简洁递归
242 class Solution:
243     def preorder(self, root: ‘Node‘) -> List[int]:
244         if not root: return []
245         res = [root.val]
246         for node in root.children:
247             res.extend(self.preorder(node))
248         return res
249 
250 # N叉树通用递归模板
251 class Solution:
252     def preorder(self, root: ‘Node‘) -> List[int]:
253         res = []
254         def helper(root):
255             if not root:
256                 return
257             res.append(root.val)
258             for child in root.children:
259                 helper(child)
260         helper(root)
261         return res
262 
263 # N叉树迭代方法
264 class Solution:
265     def preorder(self, root: ‘Node‘) -> List[int]:
266         if not root:
267             return []
268         s = [root]
269         # s.append(root)
270         res = []
271         while s:
272             node = s.pop()
273             res.append(node.val)
274             # for child in node.children[::-1]:
275             #     s.append(child)
276             s.extend(node.children[::-1])
277         return res
278 
279 
280 作者：821218213
281 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/python3-er-cha-shu-suo-you-bian-li-mo-ban-ji-zhi-s/
282 来源：力扣（LeetCode）