二叉树遍历

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

一、层序遍历

层序遍历（Level-Order Traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于广度优先遍历。

    1
   / \
  2   3           层序遍历：1 2 3 4 5 6
 / \   \
4   5   6

层序遍历的伪代码类似这样：

void levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        visit(node);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中 n 是节点的数量。每个节点恰好会被运算一次。
• 空间复杂度：O(n)，为队列的开销，队列中节点的个数不会超过 n。

二、深序遍历

深序遍历（Depth-Order Traversal）从顶部到底部遍历二叉树，并在按照一定的优先级顺序访问节点。

深序遍历本质上属于深度优先遍历。

根据遍历过程中节点访问顺序的不同，深序遍历可分为 3 种类型：

• 前序遍历：根节点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根节点 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根节点

在前中后序中，前中后指的是根节点的访问顺序。

2.1 前序遍历

前序遍历遍历顺序为：根节点 -> 左子树 -> 右子树。

    1
   / \
  2   3           前序遍历：1 2 4 5 3 6
 / \   \
4   5   6

前序遍历的伪代码类似这样：

void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 访问优先级：根节点 -> 左子树 -> 右子树
    visit(root);
    preOrder(root.left);
    preOrder(root.right);
}

复杂度分析：

• 时间复杂度：O(n)，其中 n 是节点的数量。每个节点恰好会被运算一次。
• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

2.2 中序遍历

中序遍历遍历顺序为：左子树 -> 根节点 -> 右子树。

    1
   / \
  2   3           中序遍历：4 2 5 1 3 6
 / \   \
4   5   6

中序遍历的伪代码类似这样：

void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    visit(root);
    inOrder(root.right);
}

复杂度分析：

• 时间复杂度：O(n)，其中 n 是节点的数量。每个节点恰好会被运算一次。
• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

2.3 后序遍历

后序遍历遍历顺序为：左子树 -> 右子树 -> 根节点。

    1
   / \
  2   3           后序遍历：4 5 2 6 3 1
 / \   \
4   5   6

后序遍历的伪代码类似这样：

void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    visit(root);
}

复杂度分析：

• 时间复杂度：O(n)，其中 n 是节点的数量。每个节点恰好会被运算一次。
• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

参考

https://www.hello-algo.com/chapter_tree/binary_tree_traversal/

https://time.geekbang.org/column/article/67856