此题不会做,希望有人能康康(C++)


【描述】
对于一棵包含 n 个节点的二叉树,给点每个节点的父节点编号,求后序遍历序列。

(在该题中,默认第i个点的数值是i)

【输入格式】
第一行给出节点数 n。

第二行给出 n 个数据,第 i 个数据表示第 i 个节点的父结点编号,每个数据间用空格隔开。其中 i 从 0 开始,树的根节点的父节点编号为 -1。

请注意:当第 x 个和第 y 个数据相等,且 x < y 时,则 x 为其父亲的左haizi,y 为其父亲的右haizi。

【输出格式】
给出树的后序遍历序列,数字间用空格隔开,最后一个数后面有空格。

【样例输入】
7

-1 0 0 1 1 2 2

【样例输出】
3 4 1 5 6 2 0

【数据范围】
n 在 50 以内。

挺简单的一道模板题,首先根据题意可以建立一颗二叉树(建议用结构体存储当前结点编号、左子树以及右子树编号),形如这样:

struct node {
    int p; //当前
    int l; //左
    int r; //右
}

然后就可以愉快地进行后序遍历(左-右-自己,顺序搞清楚),用个递归,如果当前结点不存在(即p为空),那么就可以返回了;反之,先搜左子树,再搜右子树,参考代码:


```c++
void nxt(int i) {
    if (!i) {
        return;
    }
    nxt(binary_tree[i].l);
    nxt(binary_tree[i].r);
    cout << binary_tree[i].p << " ";
}

代码供参考,如有错误请礼貌指出,谢谢!