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

题目链接

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

题目描述

给定一棵包含 $n$ 个节点的二叉树，给出 $n-1$ 条有向边 $u\to v$ （父到子）。对子节点的左右关系规定：

若父节点拥有两个孩子，则编号较小者为左孩子，较大者为右孩子；
若父节点仅有一个孩子，且该子节点编号大于父节点编号，则视为左孩子；否则视为右孩子。

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

输入：

第一行一个整数 $n$
接下来 $n-1$ 行，每行两个整数 $u$ 、 $v$ 表示一条有向边 $u\to v$

输出：

第一行：先序遍历序列；第二行：中序遍历序列；第三行：后序遍历序列。各行数字以单个空格分隔

解题思路

根据边构建每个节点的孩子集合；根节点为从未作为子节点出现的节点。
对每个父节点：
- 若有两个孩子，按编号小者为左，大者为右；
- 若仅一个孩子 $c$ ，若 $c>\text{parent}$ 则为左，否则为右。
按标准递归定义输出三种遍历：先序（根-左-右）、中序（左-根-右）、后序（左-右-根）。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if (!(cin >> n)) return 0;
    vector<vector<int>> children(n + 1);
    vector<int> indeg(n + 1, 0), L(n + 1, 0), R(n + 1, 0);
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        children[u].push_back(v);
        indeg[v]++;
    }
    int root = 1;
    for (int i = 1; i <= n; ++i) if (indeg[i] == 0) { root = i; break; }

    for (int u = 1; u <= n; ++u) {
        if (children[u].size() == 2u) {
            int a = children[u][0], b = children[u][1];
            if (a < b) { L[u] = a; R[u] = b; }
            else { L[u] = b; R[u] = a; }
        } else if (children[u].size() == 1u) {
            int c = children[u][0];
            if (c > u) L[u] = c; else R[u] = c;
        }
    }

    vector<int> pre, in, post;
    function<void(int)> dfsPre = [&](int u){ if (!u) return; pre.push_back(u); dfsPre(L[u]); dfsPre(R[u]); };
    function<void(int)> dfsIn  = [&](int u){ if (!u) return; dfsIn(L[u]); in.push_back(u); dfsIn(R[u]); };
    function<void(int)> dfsPost= [&](int u){ if (!u) return; dfsPost(L[u]); dfsPost(R[u]); post.push_back(u); };

    dfsPre(root); dfsIn(root); dfsPost(root);

    auto printLine = [&](const vector<int>& v){
        for (int i = 0; i < (int)v.size(); ++i) {
            if (i) cout << ' ';
            cout << v[i];
        }
        cout << '\n';
    };
    printLine(pre);
    printLine(in);
    printLine(post);
    return 0;
}

import java.util.*;

public class Main {
    static int n;
    static int[] L, R, indeg;
    static List<Integer>[] children;
    static List<Integer> pre = new ArrayList<>();
    static List<Integer> in = new ArrayList<>();
    static List<Integer> post = new ArrayList<>();

    static void dfsPre(int u) { if (u == 0) return; pre.add(u); dfsPre(L[u]); dfsPre(R[u]); }
    static void dfsIn(int u)  { if (u == 0) return; dfsIn(L[u]); in.add(u); dfsIn(R[u]); }
    static void dfsPost(int u){ if (u == 0) return; dfsPost(L[u]); dfsPost(R[u]); post.add(u); }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        children = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) children[i] = new ArrayList<>();
        indeg = new int[n + 1];
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            children[u].add(v);
            indeg[v]++;
        }
        L = new int[n + 1];
        R = new int[n + 1];
        int root = 1;
        for (int i = 1; i <= n; i++) if (indeg[i] == 0) { root = i; break; }

        for (int u = 1; u <= n; u++) {
            if (children[u].size() == 2) {
                int a = children[u].get(0), b = children[u].get(1);
                if (a < b) { L[u] = a; R[u] = b; } else { L[u] = b; R[u] = a; }
            } else if (children[u].size() == 1) {
                int c = children[u].get(0);
                if (c > u) L[u] = c; else R[u] = c;
            }
        }

        dfsPre(root); dfsIn(root); dfsPost(root);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < pre.size(); i++) { if (i > 0) sb.append(' '); sb.append(pre.get(i)); }
        System.out.println(sb.toString()); sb.setLength(0);
        for (int i = 0; i < in.size(); i++) { if (i > 0) sb.append(' '); sb.append(in.get(i)); }
        System.out.println(sb.toString()); sb.setLength(0);
        for (int i = 0; i < post.size(); i++) { if (i > 0) sb.append(' '); sb.append(post.get(i)); }
        System.out.println(sb.toString());
    }
}

import sys
sys.setrecursionlimit(1 << 20)

n = int(input().strip())
children = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for _ in range(n - 1):
    u, v = map(int, input().split())
    children[u].append(v)
    indeg[v] += 1

L = [0] * (n + 1)
R = [0] * (n + 1)
root = next(i for i in range(1, n + 1) if indeg[i] == 0)

for u in range(1, n + 1):
    if len(children[u]) == 2:
        a, b = children[u][0], children[u][1]
        if a < b:
            L[u], R[u] = a, b
        else:
            L[u], R[u] = b, a
    elif len(children[u]) == 1:
        c = children[u][0]
        if c > u:
            L[u] = c
        else:
            R[u] = c

pre, ino, post = [], [], []

def dfs_pre(u):
    if u == 0:
        return
    pre.append(u)
    dfs_pre(L[u])
    dfs_pre(R[u])

def dfs_in(u):
    if u == 0:
        return
    dfs_in(L[u])
    ino.append(u)
    dfs_in(R[u])

def dfs_post(u):
    if u == 0:
        return
    dfs_post(L[u])
    dfs_post(R[u])
    post.append(u)

dfs_pre(root)
dfs_in(root)
dfs_post(root)

print(' '.join(map(int.__str__, pre)))
print(' '.join(map(int.__str__, ino)))
print(' '.join(map(int.__str__, post)))

算法及复杂度

构建左右孩子并找根： $\mathcal{O}(n)$
三种遍历： $\mathcal{O}(n)$
总时间复杂度： $\mathcal{O}(n)$ ；空间复杂度： $\mathcal{O}(n)$