先序遍历、中序遍历和后序遍历【牛客tracker 每日一题】

先序遍历、中序遍历和后序遍历

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定一棵包含n nn个节点的二叉树，节点编号为1 ∼ n 1∼n1∼n，以n − 1 n−1n−1条有向边( a i , b i ) (a_i,b_i)(ai​,bi​)形式给出，表示父节点a i a_iai​指向子节点b i b_ibi​。

对子节点的左右关系作如下规定：

• 若父节点拥有两个孩子，则编号较小者为左孩子，较大者为右孩子；
• 若父节点仅有一个孩子，且该子节点编号大于父节点编号，则视为左孩子；否则视为右孩子。

请输出该二叉树的先序、中序、后序遍历序列。

输入描述：

第一行输入整数n ( 1 ≦ n ≦ 10 5 ) n(1≦n≦10^5)n(1≦n≦105)。
接下来n − 1 n−1n−1行，每行输入两个整数a i , b i ( 1 ≦ a i , b i ≦ n ) a_i,b_i(1≦a_i,b_i≦n)ai​,bi​(1≦ai​,bi​≦n)，表示一条有向边a i → b i a_i→b_iai​→bi​。

输出描述：

第一行输出先序遍历序列；
第二行输出中序遍历序列；
第三行输出后序遍历序列。各行序列中的数字以单个空格分隔。

示例1

输入：

2 1 2

输出：

1 2 2 1 2 1

解题思路

首先构建二叉树结构，用数组t tt存储每个节点的左右孩子，遍历输入的n − 1 n-1n−1条有向边，标记子节点v [ b ] = t r u e v[b]=truev[b]=true，按规则确定左右孩子（父节点单孩子时，子节点编号大于父节点则为左孩子，否则为右孩子；双孩子时编号较小者为左孩子）；随后找到未被标记的根节点（无父节点）；接着通过递归分别实现先序（根→左→右）、中序（左→根→右）、后序（左→右→根）遍历，依次输出对应序列；该方法通过数组高效存储节点的左右孩子，递归遍历适配n nn达1 e 5 1e51e5的规模，先完成树的构建再按遍历规则输出，精准得到三种遍历序列，满足题目对左右孩子的定义和遍历顺序的要求。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;ll t[N][2];boolv[N];voidpro(ll root){cout<<root<<" ";if(t[root][0])pro(t[root][0]);if(t[root][1])pro(t[root][1]);}voidin(ll root){if(t[root][0])in(t[root][0]);cout<<root<<" ";if(t[root][1])in(t[root][1]);}voidpost(ll root){if(t[root][0])post(t[root][0]);if(t[root][1])post(t[root][1]);cout<<root<<" ";}intmain(){ll n;cin>>n;for(ll i=1;i<n;++i){ll a,b;cin>>a>>b;v[b]=true;if(t[a][0]==0&&t[a][1]==0){if(a<b)t[a][0]=b;elset[a][1]=b;}else{if(t[a][0]){if(t[a][0]<b)t[a][1]=b;else{t[a][1]=t[a][0];t[a][0]=b;}}elseif(t[a][1]){if(t[a][1]>b)t[a][0]=b;else{t[a][0]=t[a][1];t[a][1]=b;}}}}ll root=1;for(root=1;root<=n;++root){if(!v[root])break;}pro(root);cout<<endl;in(root);cout<<endl;post(root);return0;}