二叉树的遍历算法(详细示例分析)

二叉树的遍历算法是对二叉树中节点的访问顺序的规定。主要分为三种，分别是前序遍历、中序遍历和后序遍历。

1.前序遍历

前序遍历是指先访问根节点，再依次访问左子树和右子树。用递归来实现的话，代码如下所示：

def preorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    res = []
    res.append(root.val)
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

接下来以一棵二叉搜索树为例，来说一下前序遍历的过程。二叉搜索树的结构如下所示：

     4
   /   \
  2     6
 / \   / \
1   3 5   7

按照前序遍历的规定，先访问根节点4，然后访问左子树2、1、3，访问完左子树后再访问右子树6、5、7。因此，这棵二叉搜索树的前序遍历顺序是4、2、1、3、6、5、7。

2.中序遍历

中序遍历是指先访问左子树，再访问根节点，最后访问右子树。同样用递归的方式实现，代码如下所示：

def inorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    res = []
    res += inorderTraversal(root.left)
    res.append(root.val)
    res += inorderTraversal(root.right)
    return res

还是以前面那棵二叉搜索树为例，按照中序遍历的规定，先访问左子树1、2、3，然后访问根节点4，最后访问右子树5、6、7。因此，这棵二叉搜索树的中序遍历顺序是1、2、3、4、5、6、7。

3.后序遍历

后序遍历是指先访问左子树，再访问右子树，最后访问根节点。同样使用递归的方式实现，代码如下所示：

def postorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    res = []
    res += postorderTraversal(root.left)
    res += postorderTraversal(root.right)
    res.append(root.val)
    return res

还是以前面那棵二叉搜索树为例，按照后序遍历的规定，先访问左子树1、3、2，然后访问右子树5、7、6，最后访问根节点4。因此，这棵二叉搜索树的后序遍历顺序是1、3、2、5、7、6、4。

除了上述三种遍历方式之外，还有层序遍历，即按照节点所在的层次从上到下依次访问各个节点。则使用队列即可实现，代码如下所示：

def levelOrder(root: TreeNode) -> List[List[int]]:
    if not root:
        return []
    res = []
    queue = [root]
    while queue:
        level = []
        n = len(queue)
        for i in range(n):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res

以前面那棵二叉搜索树为例，按照层序遍历的规定，先访问第一层的根节点4，然后依次访问第二层的2、6，最后依次访问第三层的1、3、5、7。因此，这棵二叉搜索树的层序遍历顺序是[[4],[2,6],[1,3,5,7]]。