Skip to content

1147: 对称二叉树

题目

题目描述

一棵有点权的有根树如果满足以下条件,则被称为对称二叉树:

* 二叉树;
* 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。

下图中给了三颗二叉树,节点内的数字为权值,节点外的 id 表示节点编号:

现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数最多。请输出这棵子树的节点数

注意:只有树根的树也是对称二叉树。本题中约定,以节点 $T$ 为子树根的一棵“子 树”指的是:节点 $T$ 和它的全部后代节点构成的二叉树。

输入格式

第一行一个正整数 $n$ ,表示给定的树的节点的数目,规定节点编号 $1 \sim n$ ,其中节点 $1$ 是树根

第二行 $n$ 个正整数,用一个空格分隔,第 $i$ 个正整数 $v_i$ 代表节点 $i$ 的权值

接下来 $n$ 行,每行两个正整数 $l_i$ , $r_i$ ,分别表示节点 $i$ 的左右孩子的编号,相互之间用空格隔开 (注意:如果一个节点不存在左孩子,则 $l_i$ 为 $-1$ ;如果一个节点不存在右孩子,则 $r_i$ 为 $-1$ )

输出格式

输出共一行,包含一个整数,表示给定的树的最大对称二叉子树的节点数

样例输入

样例输入 1

text 2 1 3 2 -1 -1 -1

样例输入 2

text 10 2 2 5 5 5 5 4 4 2 3 9 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 3 4 5 6 -1 -1 7 8

样例输出

样例输出 1

text 1

样例输出 2

text 3

数据范围

$v_i\leq 1000$, $n\leq10^6$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!