新二叉树

题意

每行给出一个节点及其左右孩子，* 表示空节点，第一行节点为根。输出前序遍历。

思路

字典 children[node]=(left,right) 保存树结构。前序遍历定义为“根、左、右”，因此递归函数直接返回：

text

1node + preorder(left) + preorder(right)

遇到 * 返回空串。

Python 知识

三字符字符串可直接解包为 node,left,right。
字典用字符节点作键，比为 26 个字母手动换算下标更自然。
root = root or node 只在第一行记录根。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：字典映射。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字符串解包与拼接。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18n = int(input())
children = {}
root = None

for _ in range(n):
    node, left, right = input().strip()
    root = root or node
    children[node] = left, right


def preorder(node):
    if node == "*":
        return ""
    left, right = children[node]
    return node + preorder(left) + preorder(right)


print(preorder(root))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
 * P1305 新二叉树
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

// 结点结构：左右孩子，'*' 表示空
struct Node {
    int l, r;
} tree[128];
bool has_parent[128];
int n;

// 前序遍历
void preorder(int u) {
    if (u == '*') return;
    putchar(u);
    preorder(tree[u].l);
    preorder(tree[u].r);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        char s[4];
        scanf("%s", s);
        int u = s[0], l = s[1], r = s[2];
        tree[u].l = l;
        tree[u].r = r;
        if (l != '*') has_parent[l] = true;
        if (r != '*') has_parent[r] = true;
    }
    // 找根：没有父结点的就是根
    int root = ' ';
    for (int c = 'a'; c <= 'z'; ++c) {
        if (tree[c].l || tree[c].r) {
            if (!has_parent[c]) { root = c; break; }
        }
    }
    preorder(root);
    putchar('\n');
    return 0;
}

复杂度

每个节点访问一次，时间复杂度 $O(n)$ ；字典与递归栈空间 $O(n)$ 。

总结

节点标签不是连续整数时，字典能直接保存树；递归代码则几乎逐字对应前序遍历定义。

目录

题意

思路

Python 知识

代码

复杂度

总结