[算法与数据结构]：二叉树的前中后序以及层序遍历（迭代，递归）的Python实现_二叉树的前序、中序、后序遍历(python实现递归和迭代)

之前写过一篇关于二叉树遍历的文章，文章中遍历结果借用yield，generator生成一系列的迭代值，用来节省内存空间。
本文是近来刷题的总结。
将二叉树的前中后序遍历的迭代和递归方法，采用最为简单直接的方法实现。

解法一：采用简单的递归，需要辅助函数
解法二：借用栈结构，将访问过的节点，置一以此避免嵌套循环，做到简单直观
解法三：解法二的优化，直接判断节点的属性即可，TreeNode or int

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
# # 解法一 递归
#         self.res=[]
#         self.inorder(root)
#         return self.res

#     def inorder(self,root):
#         if not root :
#             return []
#         self.inorder(root.left)
#         self.res.append(root.val)
#         self.inorder(root.right)
# # 解法二 迭代 颜色法 访问过的置1
#         WHITE,GRAY=0,1
#         res,stack=[],[(WHITE,root)]
#         while stack:
#             color,node=stack.pop()
#             if node is None:
#                 continue
#             if color==WHITE:
#                 # tip1:挨个带入
#                 # stack.append((WHITE,node.right))
#                 # stack.append((GRAY,node))
#                 # stack.append((WHITE,node.left))
#                 # tip2 拼接带入 简练但是速度慢
#                 stack.extend([(WHITE,node.right),(GRAY,node),(WHITE,node.left)])
#             else:
#                 res.append(node.val)
#         return res
# 解法三 类型判断性
            res,stack=[],[root]
            while stack:
                node=stack.pop()
                if isinstance(node,TreeNode):
                    stack.extend([node.right,node.val,node.left])
                elif isinstance(node,int):
                    res.append(node)
            return res

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

层序遍历：BFS 输出结果是每层一个数组结构

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # 解法 二叉树的分层打印
        from collections import deque
        if not root: return []
        res=[]
        q=deque()
        q.append(root)
        while q:
            tmp=[]
            # 循环每一层的节点
            for _ in range(len(q)):    # pop出每一层的节点 将其放入tmp中 将每个节点的左右节点放入
                a=q.popleft()
                tmp.append(a.val)
                if a.left: q.append(a.left)
                if a.right: q.append(a.right)
            res.append(tmp)
        return res
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