软件开发教程 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试
游戏开发 网络协议 系统运维 HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程
C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
 
   -> 数据结构与算法 -> 对称二叉树 -> 正文阅读

[数据结构与算法]对称二叉树

这是蒟蒻认真写的第一篇题解,如有欠缺,请理解

题目描述

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

1、二叉树;

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

下图中节点内的数字为权值,节点外的 i d id id表示节点编号。

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

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

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

第二行 n n n个正整数,用一个空格分隔,第 i i i个正整数 v [ i ] v[i] v[i]代表节点 i i i的权值。

接下来 n n n行,每行两个正整数 l [ i ] , r [ i ] l[i],r[i] l[i],r[i],分别表示节点 i i i的左右孩子的编号。如果不存在左 / 右孩子,则以 ? 1 -1 ?1表示。两个数之间用一个空格隔开。是树根。

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

接下来行,每行两个正整数,分别表示节点的左右孩子的编号。如果不存在左 / 右孩子,则以表示。两个数之间用一个空格隔开。

样例

【输入样例 1】

2
1 3
2 -1
-1 -1

【输出样例 1】

1

【输入样例 2】

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

【输出样例 2】

3

数据范围与提示

【输入输出样例 1 说明】

Alt
最大的对称二叉子树为以节点为 2 2 2树根的子树,节点数为 1 1 1

【输入输出样例2说明】
Alt
最大的对称二叉子树为以节点为 7 7 7树根的子树,节点数为 3 3 3

【数据规模与约定】
25 25 25个测试点。
v [ i ] ≤ 1000 v[i] ≤ 1000 v[i]1000
测试点 1 ~ 3 1 \sim 3 13, n ≤ 10 n ≤ 10 n10,保证根结点的左子树的所有节点都没有右孩子,根结点的右 子树的所有节点都没有左孩子。
测试点 4 ~ 8 4 \sim 8 48, n ≤ 10 n ≤ 10 n10
测试点 9 ~ 12 9 \sim 12 912, n ≤ 1 0 5 n ≤ 10^5 n105 ,保证输入是一棵“满二叉树” 。
测试点 13 ~ 16 13 \sim 16 1316, n ≤ 1 0 5 n ≤ 10^5 n105,保证输入是一棵“完全二叉树”。
测试点 17 ~ 20 17 \sim 20 1720, n ≤ 1 0 5 n ≤ 10^5 n105,保证输入的树的点权均为 11。
测试点 21 ~ 25 21 \sim 25 2125, n ≤ 1 0 6 n ≤ 10^6 n106

本题约定:

层次:节点的层次从根开始定义起,根为第一层,根的孩子为第二层。树中任一节 点的层次等于其父亲节点的层次加 1 1 1

树的深度:树中节点的最大层次称为树的深度。

满二叉树:设二叉树的深度为 h h h,且二叉树有 2 h ? 1 2^h-1 2h?1个节点,这就是满二叉树。

思路

首先,要把对称二叉树的概念搞清楚,下图有很详细的解释
Alt
对称二叉树,权值要对称,然后结构也要对称。

简单分析一下题面:对称二叉树的最大结点数,最小是 1 1 1,然后可以开始分析数据范围,不难发现输出1,3,6可以水很多分,当然3是最多的,如果是洛谷数据可以水到32分(好像是,不要问我怎么知道的),当然优秀的我们怎么可以水分,即便这是一道NOIP原题。

初始化存储在此不作赘余,相信刷到这题的树已经有些水准,关于孩子表示法双亲表示法之类的,可以使代码条理化,其实也可开几个数组

先用一个函数搜索以 i i i为结点的最大对称二叉树,建议记忆化,省时间,又方便了后面的操作,注意如果搜索到节点为 ? 1 -1 ?1则代表已经无路可搜,即为出口,直接返回,接着继续遍历,以它的两个孩子为结点。

接下来是一个 c h e c k check check函数,用以判断是否成立,现在就要用到 r [ i ] r[i] r[i]了,如果当前结点的只有一个孩子都不相同,直接跳出,若是没有孩子,返回 t r u e true true,如果有两个孩子,继续判断它们的权值(即是 v [ i ] v[i] v[i]),之后,想到对称二叉树的定义,第一个孩子的左孩子与第二个孩子的右孩子进行递归判断,第一个孩子的右孩子与第二个孩子的左孩子进行递归判断

用一个变量存储答案,寻找结点满足要求的 d p [ i ] dp[i] dp[i]最大值,最后输出, o v e r ! over! over!

最后总结一下,两个重要函数,缺一不可,第一个函数为第二个函数作铺垫,第二个函数为第一个函数返回值作判断,相辅相成。

代码时间

备注:此题题面制作不易,代码也考验思路,请先理解思路,不要直接TJ,珍惜一下作者的劳动成果,感谢您的理解

#include<bits/stdc++.h>
using namespace std;
int n,dp[1000005],ans;
struct Tree{
	int v,Lchild,Rchild;
}a[1000005];
int dfs(int x){
	if(x==-1)return 0;
	if(dp[x]!=0)return dp[x];
	return dp[x]=dfs(a[x].Lchild)+dfs(a[x].Rchild)+1;
}
bool check(int x,int y){
	int tot=0;
	if(x==-1)tot++;
	if(y==-1)tot++;
	if(tot==1)return false;
	if(tot==2)return true;
	if(a[x].v==a[y].v)return(check(a[x].Lchild,a[y].Rchild)&&check(a[y].Lchild,a[x].Rchild));
	else return false;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
	for(int i=1;i<=n;i++)scanf("%d %d",&a[i].Lchild,&a[i].Rchild);
	dfs(1);
	for(int i=1;i<=n;i++){
		if(check(a[i].Lchild,a[i].Rchild)){
			ans=max(ans,dp[i]);
		}
	}
	printf("%d",ans);
	return 0;
}

  数据结构与算法 最新文章
PTA (乙级)1035 插入与归并 (25 分)
动态规划学习
A. Find The Array
读《大话数据结构》记录Day 01
排序算法:希尔排序_代码
玩转算法(十二)——链表(删除链表)
西瓜书第四章拾遗
紫书第6章 数据结构基础 例题A~D
122 买卖股票的最佳时机-02
求二叉树最大深度
上一篇文章      下一篇文章      查看所有文章
加:2021-07-17 12:12:08  更:2021-07-17 12:14:17 
 
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年7日历 -2021/7/27 5:19:35-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件开发教程