Python 数据结构之二叉树：二叉树的遍历：DFS 深度优先（先序遍历、中序遍历、后续遍历）和 BFS 广度优先遍历。

朱雀 2023-05-22 04:46 14阅读 0赞

# 1. 二叉树 #

二叉树是一种常用的数据结构，是树这种数据机构的一种特例。它最多只有两个子节点，且如果有两个子节点，两个子节点之间是有顺序的，一个称为左孩子节点，一个称为右孩子节点。  
每个节点的构造如下：

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

其中 val 是本节点的值，left 指向左孩子节点，right 指向右孩子节点。

# 2. DFS 深度优先遍历 #

深度遍历：对于一个节点 node，在它向下的分支中选择一条分支一直走下去，知道走到叶子节点并原路返回到节点 node，再选择另一条分支走，直到没有分支可走。  
听上去有点抽象，我们从例子看看。

## 2.1 先序遍历：本节点 --> 左分支 --> 右分支 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70]  
本图来自 leetcode [树的遍历][Link 1]

1.  我们都是从根节点开始：顺序是本节点 --> 左分支 -->右分支。假设遍历结构放入数组 res 中，现在则为 \[F\]
2.  然后根节点的左分支，即为这一部分，同样的本节点 --> 左分支 -->右分支，此时 res = \[F, B\]  
    ![在这里插入图片描述][20200416095613578.png]
3.  继续左子树：这时候到达叶子节点 A，res = \[F, B, A\]
4.  然后回到 B 为根节点的子树中，此时对于这个子树，B 和 A 都已经访问了，自然进入 B 的右子树中，然后按照规则继续，则 res = \[F, B, A, D, C, E\]
5.  然后回到根节点，这个时候对于根节点来说自身和左分支已经遍历完成了，此时自然进入右分支，按照规则，最后的 res = \[F, B, A, D, C, E, G, I, H\]

## 2.2 中序遍历：左分支 --> 本节点 --> 右分支 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70]

1.  我们都是从根节点开始：顺序是左分支 --> 本节点 --> 右分支。假设遍历结构放入数组 res 中，现在则为 \[\]
2.  然后根节点的左分支，即为这一部分，同样的左分支 --> 本节点 --> 右分支，此时 res = \[\]  
    ![在这里插入图片描述][20200416095613578.png]
3.  继续左子树：这时候到达叶子节点 A，res = \[A\]
4.  然后回到 B 为根节点的子树中，此时对于这个子树，A 左分支都已经访问了，自然先遍历自身然后进入 B 的右子树中，然后按照规则继续，则 res = \[A, B, C, D, E\]
5.  然后回到根节点，这个时候对于根节点来说左分支已经遍历完成了，此时遍历自身然后进入右分支，按照规则，此时的 res = \[A, B, C, D, E, F\]
6.  此时进入根节点的右分支。此时对于以 G 为根节点的子树来说，左分支为空，所以遍历自身，进入 G 的右分支，此时 res = \[A, B, C, D, E, F, G\]  
    ![在这里插入图片描述][20200416100356488.png]
7.  后面按照规则最后结果为： \[A, B, C, D, E, F, G, H, I\]

## 2.2 后序遍历：左分支 --> 右分支 --> 本节点 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70]  
同样的图，按照规则最后结果 res = \[A, C, E, D, B, H, I, G, F\]

## 2.4 DFS 总结 ##

很多人一开始纠结这个是对于先序后序这个有误解，以为后序是右分支 --> 本节点 --> 左分支。这是错误的，我们始终记住先序，中序，后序是针对本节点相对于左分支和右分支的顺序：本左右则为先；左本右则为中，左右本则为后，关键是本节点顺序，左右之间顺序永远是左节点在前右节点在后，因为我们前面说了，二叉树是一个顺序树，左右孩子节点是有顺序的，永远的左节点在前，右节点在后，遍历同样。

# 3. BFS #

BFS 就很简单了，只需要记住从上到下逐层遍历，每一层从左往右一次遍历。因此  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70 1]  
遍历结果如下：  
res = \[F, B, G, A, D, I, C, E, H\]

# 4. 代码实现 DFS #

这里的方法总结了 4 种：递归，迭代，Morris 遍历以及 leetcode 网友贡献的颜色标记法, 可以参考[颜色标记法][Link 2]。

## 4.1 DFS 的递归实现 ##

递归实现是最容易理解的。

### 4.1.1 先序遍历 ###

对于每一个节点，先把自己的值放入 res 中，然后递归地按顺序遍历左孩子和右孩子。

class Solution:
        def preorderTraversal(self, root):
            res = []
            def PT(node):
                if not node:
                    return
                else:
                    res.append(node.val)
                    PT(node.left)
                    PT(node.right)
            if not root:
                return res
            PT(root)
            return res

### 4.1.2 中序遍历 ###

对于每一个节点，先递归遍历自己左孩子，然后把自己的值放入 res，然后递归地遍历右孩子。

class Solution:
        def inorderTraversal(self, root):
            res = []
            def IT(node):
                if not node:
                    return
                IT(node.left)
                res.append(node.val)
                IT(node.right)
            if not root:
                return res
            IT(root)
            return res

### 4.1.3 后序遍历 ###

对于每一个节点，先递归地按顺序遍历左孩子和右孩子，然后把自己的值放入 res 中。

class Solution:
        def postorderTraversal(self, root):
            res = []
            def PT(node):
                if not node:
                    return
                PT(node.left)
                PT(node.right)
                res.append(node.val)
            if not root:
                return res
            PT(root)
            return res

## 4.2 DFS 的迭代实现 ##

### 4.2.1 先序遍历 ###

class Solution:
        def preorderTraversal(self, root):
            res = []
            stack = []
            node = root
            while node or stack:
                while node:
                    res.append(node.val)
                    stack.append(node)
                    node = node.left
                node = stack.pop()
                node = node.right
            return res

### 4.2.2 中序遍历 ###

class Solution:
        def inorderTraversal(self, root):
            res = []
            node = root
            stack = []
            while node or stack:
                while node:
                    stack.append(node)
                    node = node.left
                node = stack.pop()
                res.append(node.val)
                node = node.right
            return res

### 4.2.3 后续遍历 ###

后续遍历不太好考虑，可以考虑修改先序遍历之后将 res 倒序输出。

class Solution:
        def postorderTraversal(self, root):
            res = []
            node = root
            stack = []
            while node or stack:
                while node:
                    res.append(node.val)
                    stack.append(node)
                    node = node.right
                node = stack.pop()
                node = node.left
            return res[::-1]

## 4.3 DFS 的莫里斯实现 ##

### 4.3.1 先序遍历 ###

class Solution:
        def preorderTraversal(self, root):
            res = []
            node = root
            while node:
                if not node.left:
                    res.append(node.val)
                    node = node.right
                else:
                    pre = node.left
                    while pre.right and pre.right is not node:
                        pre = pre.right
                    if not pre.right:
                        pre.right = node
                        res.append(node.val)
                        node = node.left
                    else:
                        pre.next = None
                        node = node.right
            return res

### 4.3.2 中序遍历 ###

class Solution:
        def inorderTraversal(self, root):
            res = []
            node = root
            while node:
                if not node.left:
                    res.append(node.val)
                    node = node.right
                else:
                    pre = node.left
                    while pre.right and pre.right is not node:
                        pre = pre.right
                    if not pre.right:
                        pre.right = node
                        node = node.left
                    else:
                        res.append(node.val)
                        pre.right = None
                        node = node.right
            return res

### 4.3.3 后序遍历 ###

同样的，莫里斯遍历的后序遍历通过修改前序遍历之后，反向 res 得到：

class Solution:
        def postorderTraversal(self, root):
            res = []
            node = root
            while node:
                if not node.right:
                    res.append(node.val)
                    node = node.left
                else:
                    pre = node.right
                    while pre.left and pre.left is not node:
                        pre = pre.left
                    if not pre.left:
                        pre.left = node
                        res.append(node.val)
                        node = node.right
                    else:
                        pre.left = None
                        node = node.left
            return res[::-1]

## 4.4 DFS 的颜色标记法实现 ##

### 4.4.1 先序遍历 ###

class Solution:
        def preorderTraversal(self, root):
            res = []
            WHITE, GRAY = 0, 1
            stack = [(root, WHITE)]
            while stack:
                node, color = stack.pop()
                if not node:
                    continue
                if color == WHITE:
                    stack.append([node.right, WHITE])
                    stack.append([node.left, WHITE])
                    stack.append([node, GRAY])
                else:
                    res.append(node.val)
            return res

### 4.4.2 中序遍历 ###

class Solution:
        def inorderTraversal(self, root):
            res = []
            WHITE, GRAY = 0, 1
            stack = [(root, WHITE)]
            while stack:
                node, color = stack.pop()
                if not node:
                    continue
                if color == WHITE:
                    stack.append((node.right, WHITE))
                    stack.append((node, GRAY))
                    stack.append((node.left, WHITE))
                else:
                    res.append(node.val)
            return res

### 4.4.3 后序遍历 ###

class Solution:
        def postorderTraversal(self, root):
            res = []
            WHITE, GRAY = 0, 1
            stack = [(root, WHITE)]
            while stack:
                node, color = stack.pop()
                if not node:
                    continue
                if color == WHITE:
                    stack.append((node, GRAY))
                    stack.append((node.right, WHITE))
                    stack.append((node.left, WHITE))
                else:
                    res.append(node.val)
            return res

# 5. 代码实现 BFS #

## 5.1 递归 ##

class Solution:
        def levelOrder(self, root):
            res = []
            if not root:
                return res
            def LO(node, depth):
                if len(res) == depth:
                    res.append([])
                res[depth].append(node.val)
                if node.left:
                    LO(node.left, depth + 1)
                if node.right:
                    LO(node.right, depth + 1)
            LO(root, 0)
            return res

## 5.2 迭代 ##

class Solution:
        def levelOrder(self, root):
            res = []
            if not root:
                return res
            queue = [root]
            while queue:
                list1 = []
                list2 = []
                for node in queue:
                    list1.append(node.val)
                    if node.left:
                        list2.append(node.left)
                    if node.right:
                        list2.append(node.right)
                res += list1
                queue = list2
            return res

# End #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70]: /images/20230521/5f33b21c0d0943b7bdeacb8ebc7b3c8a.png
[Link 1]: https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/7/
[20200416095613578.png]: /images/20230521/7ef5582c096b483bbfc1bd28bc6e7508.png
[20200416100356488.png]: /images/20230521/f1dabfdd54c34e40aa96013e44988a7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70 1]: /images/20230521/e907b185bbc244709dcf5d1a27aafba7.png
[Link 2]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/