对称二叉树(tree_c)

题目描述

给定二叉树的顺序存储串 s，结点按层、从左到右依次写出，空位置记作 #。若每个结点要么孩子齐全、要么没有孩子，则称该树对称。判断该树是否对称，输出 Yes 或 No。

样例输入 ABCDE 对应树 A(B(D,E),C)，每个非叶子结点都孩子齐全，输出 Yes。

思路

位置 k 的左右孩子固定落在 2k+1 与 2k+2，因此相邻位置 (1,2)、(3,4)、… 正好是一对对兄弟。把串补到长度 2n 后，逐对检查：若同一对里一个为空、一个非空，则不对称；全部同空或同非空则对称。末尾补 # 只产生同空对，不影响结果。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:30
# update_at: 2026-10-12 14:52

# 二叉树的顺序存储判对称：位置 k 的左右孩子固定在 2k+1 / 2k+2
# 串里 s[k] 是位置 k 的结点字母，'#' 是空位。把串补到 2n 长后，
# 相邻位置 (1,2)、(3,4)、... 恰好是一对对兄弟；
# 每对兄弟"同空或同非空" <=> "每个结点要么没孩子、要么孩子齐全"，就是题目的对称定义。
# 如何使用：
# 1. pad_tail(s)     末尾省略的孩子补成 '#'，只多出"同空"兄弟对，不影响判定
# 2. is_symmetric(s) 逐对兄弟检查，出现"一空一非空"就返回 False
# 3. solve()         读入 -> 补尾 -> 判定，输出 Yes / No

import sys

EMPTY = '#'             # 顺序存储里的空位置标记
BOTH_EMPTY = EMPTY * 2  # 一对兄弟都为空的样子


def pad_tail(level_order: str) -> str:
    """把串补到 2n 长：末尾省略不写的孩子补成空位。"""
    return level_order.ljust(len(level_order) * 2, EMPTY)


def is_symmetric(level_order: str) -> bool:
    """逐对兄弟检查：(2k+1, 2k+2) 是结点 k 的两个孩子，同空或同非空才对称。"""
    padded = pad_tail(level_order)
    # 兄弟对要么都为空，要么都非空；出现"一空一非空"就存在只有一个孩子的结点
    return all(padded[i:i + 2] == BOTH_EMPTY or EMPTY not in padded[i:i + 2]
               for i in range(1, len(level_order), 2))


def solve() -> None:
    level_order = sys.stdin.read().strip()
    print('Yes' if is_symmetric(level_order) else 'No')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:13
 * update_at: 2026-10-12 14:55
 */
// main.cpp：二叉树顺序存储判对称——位置 k 的孩子在 2k+1/2k+2，逐对兄弟判同空或同非空。
//
// 这题的树就存在一个字符串里，不需要再建结点结构：s[k] 是位置 k 的结点字母，
// '#' 表示空位。把串补到 2n 长后，相邻位置 (1,2)、(3,4)、... 恰好是一对对兄弟，
// 每对兄弟"同空或同非空"就等价于"每个结点要么没孩子、要么孩子齐全"，
// 正是题目给的对称定义。

#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;

const int maxn = 100005; // 题面没给串长上限，按 1e5 留余量（串中一位对应一个结点或空位）

char s[maxn * 2]; // 顺序存储串，s[k] 是位置 k 的结点字母，'#' 是空位；末尾会补 '#' 到 2n 长
ll n;             // 原串长度（补 '#' 之前）

// 末尾省略不写的孩子补成空位。补出来的位置只会增加"同空"的兄弟对，不影响判定
void pad_tail() {
    ll len = strlen(s);
    while (len < 2 * n) {
        s[len] = '#';
        len++;
    }
    s[len] = '\0'; // 补完封口，后面继续按 C 字符串遍历
}

// 逐对兄弟检查：(2k+1, 2k+2) 是结点 k 的两个孩子。
// 一对里出现"一个空、一个非空"，就说明有结点只有一个孩子，树不对称
bool is_symmetric() {
    ll len = strlen(s);
    for (ll i = 1; i + 1 < len; i += 2) {
        bool left_empty = (s[i] == '#');
        bool right_empty = (s[i + 1] == '#');
        if (left_empty != right_empty) {
            return false;
        }
    }
    return true;
}

void solve() {
    cin >> s;
    n = strlen(s);
    pad_tail();
    if (is_symmetric()) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

对称二叉树(tree_c)

目录

题目描述

思路

参考代码