题解 | #先序遍历、中序遍历和后序遍历#

先序遍历、中序遍历和后序遍历

https://www.nowcoder.com/practice/15fdb346838545d0b272e43957e1cb2a

题目链接

先序遍历、中序遍历和后序遍历

题目描述

给定一棵包含 $N$ 个节点的二叉树，以 $N-1$ 条有向边 $u \to v$ （父节点指向子节点）的形式给出。子节点的左右关系需要根据以下规则确定：

若父节点有两个孩子，编号较小者为左孩子，较大者为右孩子。
若父节点只有一个孩子：
- 若子节点编号大于父节点编号，则该孩子为左孩子。
- 否则（子节点编号小于父节点编号），该孩子为右孩子。

你需要输出该二叉树的先序、中序、后序遍历序列。

解题思路

本题的解法分为两个主要步骤：1. 重建二叉树结构 和 2. 执行标准遍历。

1. 重建二叉树

首先，我们需要根据输入的父子关系和给定的左右孩子规则，构建出完整的二叉树。

寻找根节点：

树的根节点是唯一没有父节点的节点。我们可以通过计算每个节点的入度来找到它。遍历所有 $N-1$ 条边 $u \to v$ ， $v$ 的入度加一。最后，入度为 $0$ 的那个节点就是根。
确定左右孩子：

a. 我们先用一个临时的邻接表（例如 $\mathit{children}[N+1]$ ）来存储每个节点的所有孩子，暂时不区分左右。

b. 然后，遍历所有节点 $i$ （从 $1$ 到 $N$ ），查看 $\mathit{children}[i]$ 列表：

有两个孩子：对 $\mathit{children}[i]$ 进行排序，第一个（较小的）是左孩子，第二个（较大的）是右孩子。

只有一个孩子 $c$ ：根据规则 $c > i$ ，判断 $c$ 是左孩子还是右孩子。

没有孩子：该节点是叶子节点。

c. 将最终确定的左右孩子关系存储在两个数组 $\mathit{left}[N+1]$ 和 $\mathit{right}[N+1]$ 中。 $\mathit{left}[i]$ 存储节点 $i$ 的左孩子编号， $\mathit{right}[i]$ 存储右孩子编号。没有孩子则记为 $0$ 或 $-1$ 。

2. 执行遍历

当二叉树的结构（即每个节点的左右孩子是谁）完全确定后，我们就可以从根节点开始，执行三种经典的深度优先遍历：

先序遍历 (Pre-order): 访问顺序是 根 $\to$ 左子树 $\to$ 右子树。
中序遍历 (In-order): 访问顺序是 左子树 $\to$ 根 $\to$ 右子树。
后序遍历 (Post-order): 访问顺序是 左子树 $\to$ 右子树 $\to$ 根。

这三种遍历都可以通过简单的递归函数实现。每个函数都接收一个当前节点作为参数，并按照各自的顺序递归调用自身处理左右子树，并在合适的时机将当前节点的值存入结果列表。

最后，按顺序输出三个遍历结果列表即可。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int left_child[100005], right_child[100005];
vector<int> pre_order_result, in_order_result, post_order_result;

void pre_order(int u) {
    if (u == 0) return;
    pre_order_result.push_back(u);
    pre_order(left_child[u]);
    pre_order(right_child[u]);
}

void in_order(int u) {
    if (u == 0) return;
    in_order(left_child[u]);
    in_order_result.push_back(u);
    in_order(right_child[u]);
}

void post_order(int u) {
    if (u == 0) return;
    post_order(left_child[u]);
    post_order(right_child[u]);
    post_order_result.push_back(u);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> in_degree(n + 1, 0);
    vector<vector<int>> children(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        children[u].push_back(v);
        in_degree[v]++;
    }

    int root = -1;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            root = i;
            break;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (children[i].empty()) continue;
        if (children[i].size() == 2) {
            sort(children[i].begin(), children[i].end());
            left_child[i] = children[i][0];
            right_child[i] = children[i][1];
        } else { // size == 1
            int child = children[i][0];
            if (child > i) {
                left_child[i] = child;
            } else {
                right_child[i] = child;
            }
        }
    }

    pre_order(root);
    in_order(root);
    post_order(root);

    for (int i = 0; i < n; ++i) cout << pre_order_result[i] << (i == n - 1 ? "" : " ");
    cout << "\n";
    for (int i = 0; i < n; ++i) cout << in_order_result[i] << (i == n - 1 ? "" : " ");
    cout << "\n";
    for (int i = 0; i < n; ++i) cout << post_order_result[i] << (i == n - 1 ? "" : " ");
    cout << "\n";

    return 0;
}

import java.util.*;

public class Main {
    static int[] leftChild, rightChild;
    static List<Integer> preOrderResult, inOrderResult, postOrderResult;

    public static void preOrder(int u) {
        if (u == 0) return;
        preOrderResult.add(u);
        preOrder(leftChild[u]);
        preOrder(rightChild[u]);
    }

    public static void inOrder(int u) {
        if (u == 0) return;
        inOrder(leftChild[u]);
        inOrderResult.add(u);
        inOrder(rightChild[u]);
    }

    public static void postOrder(int u) {
        if (u == 0) return;
        postOrder(leftChild[u]);
        postOrder(rightChild[u]);
        postOrderResult.add(u);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] inDegree = new int[n + 1];
        List<Integer>[] children = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            children[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            children[u].add(v);
            inDegree[v]++;
        }

        int root = -1;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                root = i;
                break;
            }
        }

        leftChild = new int[n + 1];
        rightChild = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (children[i].isEmpty()) continue;
            if (children[i].size() == 2) {
                Collections.sort(children[i]);
                leftChild[i] = children[i].get(0);
                rightChild[i] = children[i].get(1);
            } else { // size == 1
                int child = children[i].get(0);
                if (child > i) {
                    leftChild[i] = child;
                } else {
                    rightChild[i] = child;
                }
            }
        }

        preOrderResult = new ArrayList<>();
        inOrderResult = new ArrayList<>();
        postOrderResult = new ArrayList<>();

        preOrder(root);
        inOrder(root);
        postOrder(root);

        for (int i = 0; i < n; i++) System.out.print(preOrderResult.get(i) + (i == n - 1 ? "" : " "));
        System.out.println();
        for (int i = 0; i < n; i++) System.out.print(inOrderResult.get(i) + (i == n - 1 ? "" : " "));
        System.out.println();
        for (int i = 0; i < n; i++) System.out.print(postOrderResult.get(i) + (i == n - 1 ? "" : " "));
        System.out.println();
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(100005)

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)
    if n == 0: return

    in_degree = [0] * (n + 1)
    children = [[] for _ in range(n + 1)]
    
    edges = []
    for _ in range(n - 1):
        edges.append(list(map(int, sys.stdin.readline().split())))

    for u, v in edges:
        children[u].append(v)
        in_degree[v] += 1
        
    root = -1
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            root = i
            break
    
    left_child = [0] * (n + 1)
    right_child = [0] * (n + 1)
    
    for i in range(1, n + 1):
        if not children[i]: continue
        if len(children[i]) == 2:
            children[i].sort()
            left_child[i] = children[i][0]
            right_child[i] = children[i][1]
        else: # len == 1
            child = children[i][0]
            if child > i:
                left_child[i] = child
            else:
                right_child[i] = child

    pre_order_result = []
    in_order_result = []
    post_order_result = []

    def pre_order(u):
        if u == 0: return
        pre_order_result.append(u)
        pre_order(left_child[u])
        pre_order(right_child[u])

    def in_order(u):
        if u == 0: return
        in_order(left_child[u])
        in_order_result.append(u)
        in_order(right_child[u])

    def post_order(u):
        if u == 0: return
        post_order(left_child[u])
        post_order(right_child[u])
        post_order_result.append(u)

    pre_order(root)
    in_order(root)
    post_order(root)

    print(*pre_order_result)
    print(*in_order_result)
    print(*post_order_result)

solve()

算法及复杂度

算法：构建邻接表、根据规则确定左右孩子、递归进行三种DFS遍历。
时间复杂度： $\mathcal{O}(N)$ 。
- 读入数据、计算入度、构建初始邻接表，需要 $\mathcal{O}(N)$ 。
- 寻找根节点需要 $\mathcal{O}(N)$ 。
- 遍历所有节点确定左右孩子关系，总共访问所有边一次，复杂度为 $\mathcal{O}(N)$ 。
- 三次遍历（先序、中序、后序）都分别访问每个节点一次，总共是 $\mathcal{O}(N)$ 。
- 总体时间复杂度为 $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(N)$ 。
- 需要空间存储入度、临时邻接表、左右孩子数组以及遍历结果，都是 $\mathcal{O}(N)$ 。
- 递归遍历的调用栈深度在最坏情况下（链状树）也是 $\mathcal{O}(N)$ 。