[NOIP2018 PJ T4]对称二叉树

短命女 2021-12-09 21:13 238阅读 0赞

**题目大意：**问一棵有根带权二叉树中最大的对称二叉树子树，对称二叉树为需满足将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。

**题解：**在对称二叉树中，对于深度相同的两个节点$u,v$，必定有$ls(u)=rs(v)$，$rs(u=ls(v)$，并且$val(u)=val(v)$，对每个点跑一遍深搜就可以了。发现跑一个点最多遍历它子树中较少的一棵子树。复杂度为$O(n\\log\_2n)$

**卡点：**无

**C++ Code：**

#include <iostream>
    #define maxn 1000010
    #define ls(u) son[0][u]
    #define rs(u) son[1][u]
    int N, n, ans;
    int V[maxn], son[2][maxn], sz[maxn];
    bool check(int u, int v) {
    	if (!~u && !~v) return true;
    	if (~u && ~v && V[u] == V[v] && check(ls(u), rs(v)) && check(rs(u), ls(v))) return true;
    	return false;
    }
    void dfs(int u) {
    	sz[u] = 1;
    	if (~ls(u)) dfs(ls(u)), sz[u] += sz[ls(u)]; 
    	if (~rs(u)) dfs(rs(u)), sz[u] += sz[rs(u)]; 
    }
    int main() {
    	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    	std::cin >> n;
    	for (int i = 1; i <= n; ++i) std::cin >> V[i];
    	for (int i = 1; i <= n; ++i) std::cin >> ls(i) >> rs(i);
    	dfs(1);
    	for (int i = 1; i <= n; ++i)
    		if (check(ls(i), rs(i))) ans = std::max(ans, sz[i]);
    	std::cout << ans << '\n';
    	return 0;
    }

转载于:https://www.cnblogs.com/Memory-of-winter/p/11076938.html

发表评论取消回复

表情：

评论列表（有 0 条评论，238人围观）

还没有评论，来说两句吧...

相关阅读

相关对称二叉树

一、问题描述给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 `[1,2,2,3,4,4,3]` 是对称的。 1 / \ 2

以你之姓@/ 2023年11月16日 06:13/ 0 赞/ 200 阅读

相关对称二叉树

目录题目示例示例 1：示例 2：提示开始解题 1.题目图示理解 2.解题思路 (宝子们,这是重点!!!) 3.解题代码 4.运行结果(p

曾经终败给现在/ 2023年10月14日 16:24/ 0 赞/ 117 阅读

相关对称二叉树

对称二叉树问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

女爷i/ 2023年10月07日 13:59/ 0 赞/ 132 阅读

相关对称二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。非递归：使用队列 / struct Tree

àì夳堔傛蜴生んèń/ 2023年02月21日 06:08/ 0 赞/ 58 阅读

相关对称二叉树

对称二叉树 1、参考资料 https://leetcode-cn.com/problems/symmetric-tree/ 2、题目要求 > 题目描述给

男娘i/ 2022年12月08日 15:52/ 0 赞/ 279 阅读

相关二叉树应用_二叉树镜像（对称）

题目：完成一个函数，输入一个二叉树，该函数输出它的镜像。如： ![这里写图片描述][70] 分析：对于一个二叉树的镜像过程，我们可以先前序遍历这棵树的每一个节点，

- 日理万妓/ 2022年05月22日 02:42/ 0 赞/ 342 阅读

相关对称二叉树

题目描述给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。 1 / \ 2 2

ゝ一纸荒年。/ 2022年02月27日 06:42/ 0 赞/ 323 阅读

相关 NOIP2018PJ T3 摆渡车

[题目链接][Link 1] 题意：时间轴上分布着$n$位乘客，$i$号乘客的位置为$t\_i$，用互相距离不小于$m$的车次将时间轴分为若干部分并管辖上一个区

傷城~/ 2021年12月11日 23:32/ 0 赞/ 212 阅读

相关 [NOIP2018 PJ T4]对称二叉树

题目大意：问一棵有根带权二叉树中最大的对称二叉树子树，对称二叉树为需满足将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。题解：在对称二叉树中，对于深

短命女/ 2021年12月09日 21:13/ 0 赞/ 239 阅读

相关二叉树之对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 / public class TreeNode

￡神魔★判官ぃ/ 2021年09月18日 05:04/ 0 赞/ 494 阅读