二叉树的后序遍历(Postorder Traversal)

题目描述

后序遍历是二叉树三种基本遍历方式之一，它的访问顺序是：

左子树 → 右子树 → 根节点

也就是：每当来到一个节点，先递归遍历它的左子树，再递归遍历它的右子树，最后才访问（输出）它自己。根节点总是在它的两棵子树都遍历完之后才被访问，因此根节点一定排在序列的最后。

现在给你一棵二叉树，请你输出它的后序遍历序列。

输入格式

第一行一个整数 n，表示二叉树的节点个数，节点编号为 1 ~ n，其中 1 号节点是根节点。

接下来 n 行，第 i 行两个整数 l 和 r，分别表示编号为 i 的节点的左孩子和右孩子的编号。如果没有左孩子（或右孩子），对应位置为 0。

输出格式

输出一行，包含 n 个整数，表示后序遍历的节点编号，相邻两个数之间用一个空格隔开。

样例输入

7
2 3
4 5
0 0
6 7
0 0
0 0
0 0

样例输出

6 7 4 5 2 3 1

数据范围

• 1 ≤ n ≤ 1000
• 输入保证构成一棵以 1 为根的合法二叉树

提示

后序遍历的递归框架是：

dfs(节点 u):
    如果 u == 0: 返回
    dfs(左孩子)
    dfs(右孩子)
    输出 u          // 后序：最后处理根

后序遍历常用于"先处理完子节点、再处理父节点"的场景，比如计算子树大小、释放整棵树等。