3348. 树的双亲存储法

LzQuarter
#include<iostream>
#include<vector>
using namespace std;
vector<int> sons[100001];//存每个节点的子节点列
int ctr = 0;
void vis(int a){
    for(int i = 0; i < sons[a].size(); i++){
        vis(sons[a][i]);
    }
    if(ctr++){
        cout << " ";
    }
    cout << a;
}
int main(){
    int N;
    cin >> N;

    for(int i = 0; i < N; i++){
        int temp;
        cin >> temp;
        if(temp != -1){
            sons[temp].insert(sons[temp].end(), i);
        }
    }
    vis(0);
    return 0;
}
wzf2018

我去,看了第二组数据,编号为1的节点父亲是编号932的节点,根本不是按题意构造的
太假了

Deuchie

这题根结点是 0 啊?

Gottfried_Leibniz

非二叉树情形的后序遍历只需要从左至右遍历整个子树,再访问根节点即可
题目是按输入父节点的顺序对各节点编号的
只需要额外记忆各节点的子节点,以及整棵树根节点的位置
附上比较易懂的C++solution

#include <iostream>
#include <vector>

using namespace std;
struct leaf{
    int32_t parent;
    vector<int32_t> sons;
};
void order(const vector<leaf>& tree, const int32_t& root);
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int32_t n,val,root;
    leaf temp;
    cin >> n;
    vector<leaf> tree;
    for(int32_t i = 0; i < n; i++){
        tree.push_back(temp);
    }
    for(int32_t i = 0; i < n; i++){
        cin >> tree[i].parent;
        if(tree[i].parent >= 0){
            tree[tree[i].parent].sons.push_back(i);
        }else{
            root = i;
        }
    }
    order(tree,root);
    return 0;
}

void order(const vector<leaf>& tree, const int32_t& root)
{
    for(int32_t i = 0; i < tree[root].sons.size(); i++){
        order(tree,tree[root].sons[i]);
    }
    cout << root << " ";
}
Deuchie

思路是从题给的形式转换为记录子结点的形式(也就是常用的形式),然后后序遍历。

#include "bits/stdc++.h"
using namespace std;
using u32 = uint32_t;
vector<vector<u32>> nodes;
inline void print_post_walk(u32 pos) {
    for (auto child: nodes[pos]) { print_post_walk(child); }
    cout << pos << ' ';
}
int main() {
    u32 n; cin >> n;
    nodes.resize(n);
    { u32 ignore; cin >> ignore; }
    for (u32 i = 1; i != n; ++i) {
        u32 parent; cin >> parent;
        nodes[parent].push_back(i);
    }
    print_post_walk(0);
}
10175102262 LarsPendragon

如沈大佬所说的话,根据我和我的室友进行的~深入~讨论,似乎只能建树然后后序遍历了。注意每一层内依然是递增编号(这是当然的吧)
附部分代码:

typedef struct child{struct tree *tre; struct child* next;}CHILD;//子节点链表
typedef struct tree{int data; struct child* c; struct child* last;}TREE;//last表示当前该树的最后一个子节点

TREE *t=(TREE*)malloc(sizeof(TREE)*n);
for(i=0; i<n; i++)
{
    int x;
    scanf("%d",&x);
    if(i>0)
    {
        TREE* curr=&t[x];
        CHILD* m=(CHILD*)malloc(sizeof(CHILD));
        m->tre=&(t[i]);
        m->next=NULL;
        if(curr->last == NULL)
            curr->c=m;
        else
            curr->last->next=m;
        curr->last=m;
    }
}
10175102211

题目里说的编号是假的,实际上并没有按层次编号

6324upup

佛了。是真的坑人 我还以为是我语文水平出了问题

你当前正在回复 博客/题目
存在问题!