二叉树的遍历方式

二叉树的遍历方式可以分为前序遍历（先序遍历）、中序遍历、后序遍历和层次遍历。前3种遍历方式的“序”指的是父节点相对于左右子节点的顺序。前序遍历就是先遍历父节点，之后再遍历左右节点；中序则是先访问左节点，再访问父节点最后访问右节点；后序是先遍历左右节点，最后访问父节点。层次遍历就是安装从上到下、从左到右顺序访问二叉树的每个节点。

从效果上来说，前序遍历相当于先访问到叶子节点后回溯到上一个节点，然后再访问到下一个叶子节点，即等价于深度优先遍历(DFS)。而层次遍历则是按层依次访问，等价于广度优先遍历(BFS)。

在本文里，将使用Python语言里实现前序、中序和后序遍历以及层次遍历，其中前序、中序和后序有递归和非递归两种实现方式。用牛客里的BM 23 二叉树的前序遍历， BM 24 二叉树的中序遍历， BM 25 二叉树的后序遍历和BM 26 二叉树的层序遍历的通过情况检验所实现算法的正确性和完备性。

递归的顺序遍历实现

对于递归版本的前序遍历、中序遍历和后序遍历实现是比较直观易懂的，只需要按照定义正常实现逻辑即可。

前序遍历

即先访问当前节点，再访问左节点和右节点。实现如下：

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def _preorderTraversal(self, node: TreeNode, result: List[int]):
        if node is None:
            return None
        
        result.append(node.val)
        self._preorderTraversal(node.left, result)
        self._preorderTraversal(node.right, result)

    def preorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        self._preorderTraversal(root, result)
        return result

中序遍历

即先访问当前节点的左节点，再访问当前节点，最后访问当前节点的右节点。实现如下：

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def _inorderTraversal(self, node: TreeNode, result: List[int]):
        if node is None:
            return None

        self._inorderTraversal(node.left, result)
        result.append(node.val)
        self._inorderTraversal(node.right, result)


    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        self._inorderTraversal(root, result)
        return result

后序遍历

即先访问当前节点的左右节点，再访问当前节点。

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def _postorderTraversal(self, node: TreeNode, result: List[int]):
        if node is None:
            return None
        
        self._postorderTraversal(node.left, result)
        self._postorderTraversal(node.right, result)
        result.append(node.val)

    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        self._postorderTraversal(root, result)
        return result

非递归的顺序遍历实现

既然递归的方法直观易懂，那为什么还要实现非递归版本呢？主要有两点原因：一是函数递归依赖于栈，而这个栈是有深度限制的。比如Linux下栈空间超过8MB就会stack overflow了，所以递归版本能解决的问题规模是受限的。二是非递归是一种审视二叉树顺序遍历的新视角，从这个视角来看二叉树遍历能明白一些遍历规则之外的东西。比如前序遍历实际相当于对二叉树进行深度优先搜索。

前序遍历

前面说到前序遍历是相当于深度优先搜索，那编写一个深度优先搜索算法即可。

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def preorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        stack = [] # 辅助栈
        result = []
        
        if root is not None:
            stack.append(root)

        while len(stack) > 0:
            node = stack.pop()
            result.append(node.val)

            # 注意这里是栈，要先访问左节点需要后压入左节点
            if node.right is not None:
                stack.append(node.right)
            if node.left is not None:
                stack.append(node.left)

        return result

中序遍历

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        stack = []
        
        while root is not None or len(stack) > 0:
            # 找到最左节点
            while root is not None:
                stack.append(root)
                root = root.left
            # 访问最左节点
            node = stack.pop()
            result.append(node.val)

            # 访问该节点的右子树
            root = node.right
        return result

后序遍历

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        stack = []
        pre = None

        while root is not None or len(stack) > 0:
            # 找到最左边的节点
            while root is not None:
                stack.append(root)
                root = root.left
            
            # 此时栈顶是当前子树最左边的节点
            node = stack.pop()

            # 查看该节点右子树情况
            if node.right is None or node.right is pre:
                # 无右子树或右子树已经访问完毕
                result.append(node.val)
                # 记录为已访问
                pre = node
            else:
                # 该节点入栈
                stack.append(node)
                # 进入右子树根节点
                root = node.right
        return result

层次遍历实现

层次遍历二叉树

层次遍历即广度优先搜索，可以使用队列实现。

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        current_layer = [root]
        next_layer = []
        result = [[root.val]]

        while len(current_layer) > 0 or len(next_layer) > 0:
            if len(current_layer) == 0:
                current_layer = next_layer
                next_layer = []
                result.append([node.val for node in current_layer])
            
            # 先进先出
            while len(current_layer) > 0:
                node = current_layer.pop(0)
                if node.left is not None:
                    next_layer.append(node.left)
                if node.right is not None:
                    next_layer.append(node.right)
        return result

之字形遍历二叉树

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return int整型二维数组
#
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        # write code here
        if pRoot is None:
            return []
        current_layer = [pRoot]
        next_layer = []
        result = [[pRoot.val]]
        # 反转标记
        reversal = True

        while len(current_layer) > 0 or len(next_layer) > 0:
            if len(current_layer) == 0:
                current_layer = next_layer
                next_layer = []
                row = [node.val for node in current_layer]
                if reversal:
                    row = row[::-1]
                result.append(row)
                reversal = not reversal
            
            # 先进先出
            while len(current_layer) > 0:
                node = current_layer.pop(0)
                if node.left is not None:
                    next_layer.append(node.left)
                if node.right is not None:
                    next_layer.append(node.right)
        return result