对称二叉树

GitHub跳转原题关系图返回列表

求点权有根树中最大的对称二叉子树：枚举对称中心，自底向上镜像判定（左右子树互换后同构且点权相同），记忆化 + 迭代栈，O(n^2)。

OJ: roj

题目 ID: 3657

难度:提高+/省选-

标签:树二叉树记忆化搜索NOIP

创建: 2026-10-02 14:15

更新: 2026-10-10 11:30

目录

  1. 形式化题目
  2. 正解
    1. 思路
      1. 代码
      2. 复杂度
    2. 总结

    形式化题目

    nn 个节点的有根树，每个节点有左右孩子指针与点权。若一棵子树是二叉树且左右子树互为镜像（结构与点权对称），称其为对称二叉树。求节点数最多的对称二叉子树的节点数。

    正解

    思路

    1. 镜像判定

    两棵子树 a,ba,b 互为镜像   ⟺  \iff L[a] 与 R[b] 互为镜像且 R[a] 与 L[b] 互为镜像，且对应点权相等。自底向上递推，同一节点对只算一次（记忆化）。

    2. 枚举中心

    对每个节点作为「对称中心」，检查其左右子树互为镜像；中心也可以是点权对称的相邻两节点（按题面定义）。答案取所有成立情形的最大节点数。

    递归深度可能达到 nn，用显式栈模拟两阶段展开（先下探子对、回收时汇总）避免 Python 递归限制。

    代码

    cpp
    /**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> VAL,Lc,Rc; map<pair<int,int>, bool> MEMO;
bool mirror_tree(int a,int b){ if(a<0||b<0) return a<0&&b<0; vector<array<int,3> > st; st.push_back({a,b,0}); while(!st.empty()){array<int,3> cur=st.back(); st.pop_back(); int x=cur[0],y=cur[1],stage=cur[2]; if(x<0||y<0) continue; pair<int,int> key={x,y}; if(stage){int lx=Lc[x], ry=Rc[y], rx=Rc[x], ly=Lc[y]; bool aok=MEMO.count({lx,ry})?MEMO[{lx,ry}]:(lx<0&&ry<0); bool bok=MEMO.count({rx,ly})?MEMO[{rx,ly}]:(rx<0&&ly<0); MEMO[key]=aok&&bok;} else if(MEMO.count(key)) continue; else if(VAL[x]!=VAL[y]) MEMO[key]=false; else {st.push_back({x,y,1}); st.push_back({Lc[x],Rc[y],0}); st.push_back({Rc[x],Lc[y],0});}} return MEMO[{a,b}];}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n; if(!(cin>>n)) return 0; VAL.assign(n+1,0); for(int i=1;i<=n;i++) cin>>VAL[i]; Lc.assign(n+1,0); Rc.assign(n+1,0); for(int i=1;i<=n;i++) cin>>Lc[i]>>Rc[i]; vector<int> order, st; st.push_back(1); while(!st.empty()){int x=st.back();st.pop_back(); order.push_back(x); if(Lc[x]>0) st.push_back(Lc[x]); if(Rc[x]>0) st.push_back(Rc[x]);} vector<int> sz(n+1); int best=0; for(int i=(int)order.size()-1;i>=0;i--){int x=order[i]; int sub=1+(Lc[x]>0?sz[Lc[x]]:0)+(Rc[x]>0?sz[Rc[x]]:0); sz[x]=sub; if(sub>best && mirror_tree(Lc[x],Rc[x])) best=sub;} cout<<best<<'\n'; return 0;}
    python
    #!/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-10-02 13:52
# update_at: 2026-10-02 13:52

import sys

VAL: list[int] = []  # 点权，下标即节点编号，0 号位补 0 占位
L: list[int] = []    # 左孩子编号，-1 表示不存在
R: list[int] = []    # 右孩子编号，-1 表示不存在
# 镜像判定缓存：同一对节点只展开一次，key = (a, b)
MEMO: dict[tuple[int, int], bool] = {}


def mirror(a: int, b: int) -> bool:
    """以 a、b 为根的两棵子树是否互为镜像（交换后结构与点权都相同）。"""
    if a < 0 or b < 0:  # 只有一侧为空就谈不上镜像
        return a < 0 and b < 0
    stack: list[tuple[int, int, int]] = [(a, b, 0)]  # (节点对, 阶段)：0 去下探，1 回收
    while stack:
        x, y, stage = stack.pop()
        if x < 0 or y < 0:  # 空树对的结论即时成立，不占缓存
            continue
        key = (x, y)
        if stage:  # 两个子对已在栈上方判完，按子对结果汇总
            lx, ry = L[x], R[y]
            rx, ly = R[x], L[y]
            MEMO[key] = MEMO.get((lx, ry), lx < 0 and ry < 0) and MEMO.get(
                (rx, ly), rx < 0 and ly < 0
            )
        elif key in MEMO:  # 该节点对早已判定，直接复用
            continue
        elif VAL[x] != VAL[y]:  # 根权不同，不必再看子树
            MEMO[key] = False
        else:  # 下探两对交叉孩子：左对右、右对左
            stack.append((x, y, 1))
            stack.append((L[x], R[y], 0))
            stack.append((R[x], L[y], 0))
    return MEMO[(a, b)]


def largest_symmetric() -> int:
    """后序累计子树大小，返回对称子树里最大的节点数。"""
    order: list[int] = []
    stack = [1]
    while stack:  # 迭代先序收集遍历序，倒着走就是孩子先于父亲
        x = stack.pop()
        order.append(x)
        if L[x] > 0:
            stack.append(L[x])
        if R[x] > 0:
            stack.append(R[x])

    size = [0] * len(VAL)
    best = 0
    for x in reversed(order):
        left, right = L[x], R[x]
        size[x] = sub = 1 + (size[left] if left > 0 else 0) + (size[right] if right > 0 else 0)
        can_beat = sub > best  # 更小的候选更新不了答案，连镜像判定一起省掉
        if can_beat and mirror(left, right):
            best = sub
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    global VAL, L, R
    n = next(data)  # 节点数，编号 1~n，1 是树根
    VAL = [0] + [next(data) for _ in range(n)]
    L = [0] * (n + 1)
    R = [0] * (n + 1)
    for i in range(1, n + 1):  # 第 i 行是节点 i 的左、右孩子编号
        L[i] = next(data)
        R[i] = next(data)
    print(largest_symmetric())


if __name__ == "__main__":
    solve()

    复杂度

    • 时间复杂度：O(n2)O(n^2) 最坏（每个中心线性验证，记忆化共享子对）。
    • 空间复杂度：O(n)O(n)。

    总结

    • 「对称子树」= 镜像同构判定 + 枚举中心，镜像关系传递成记忆化子问题。
    • Python 树递归一律显式栈两阶段（下探/回收），规避递归深度与栈开销。