二叉树的后序遍历 题目ID：8803

问题讨论区 基础段
1

题目描述

给定一颗以1为根的二叉树，输出他的后序遍历

输入格式

第一行一个正整数n表示节点个数
接下来n行，第i行两个正整数分别表示节点i的左右儿子，如果没有儿子为-1

输出格式

一行，n个正整数表示答案

样例

Input 1

3
2 3
-1 -1
-1 -1

Output 1

2 3 1

样例解释

输入样例1解释：
根据输入，我们可以构建以下二叉树：
1
/
2 3
所以，后序遍历的结果是2 3 1。

数据范围

1<=n<=100

谁来教教我！！！

1 个赞
2

你先序遍历过了吗

1 个赞
3

循环输入左右孩子 还是一样

for(int i=1; i<=n; i++) {
		int l,r;
		cin>>l>>r;
		if(l!=-1) {
			tree[i*2]=l;
		}
		if(r!=-1) {
			tree[i*2+1]=r;
		}
	}

但先序的dfs函数部分是：

void dfs(int x) {
	cout<<x<<' ';
	if(tree[x*2])dfs(tree[2*x]);
	if(tree[x*2+1])dfs(tree[2*x+1]);
}

后序是：

void dfs(int x) {
	if(tree[x*2])dfs(tree[2*x]);
	if(tree[x*2+1])dfs(tree[2*x+1]);
	cout<<x<<' ';
}
1 个赞
4

哥他是-1不是0啊

5

谢谢