由parent数组构建树

Posted on | In |

有些情况下，一棵树用节点的父节点信息来表示，而很多算法都需要从根出发，去访问节点，于是乎需要前者向后者的转换。

不过，这种算法，估计就是那种很经典，看过就不会忘的，就直接参考网上的了：
https://www.geeksforgeeks.org/construct-a-binary-tree-from-parent-array-representation/

基本思想

记录每个节点的指针：nodeP

当节点尚未生成，即nodeP还为null，生成一个节点，将其父节点指针对应孩子指向它，如果此时父节点并未生成，那么递归的生成

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//
// Created by Zhao Xiaodong on 2018/8/26.
//
#include <vector>
#include <queue>
#include <iostream>
#include <climits>
using namespace std;
struct Node {
    int k;
    vector<Node *> children;
    Node(int key) : k(key) {}
};
void createNode(int i, vector<int> &parent, vector<Node *>& nodeP) {
    if (nodeP[i])
        return;
    nodeP[i] = new Node(i);
    if (parent[i] != -1) {
        if (!nodeP[parent[i]])
            createNode(parent[i], parent, nodeP);
        nodeP[parent[i]]->children.push_back(nodeP[i]);
    }
}
Node *constructTree(vector<int> &parent) {
    vector<Node *> nodeP(parent.size(), nullptr);
    for (int i = 0; i < parent.size(); i++) {
        createNode(i, parent, nodeP);
    }
    Node *root = nullptr;
    for (int i = 0; i < parent.size(); i++) {
        if (parent[i] == -1)
            root = nodeP[i];
    }
    return root;
}
void levelPrint(Node *root) {
    if (!root)
        cout << "NULL";
    else {
        queue<Node *> q;
        Node *marker = nullptr;
        q.push(root);
        q.push(marker);
        while (!q.empty()) {
            while (q.front()) {
                Node *node = q.front();
                q.pop();
                cout << node->k << " ";
                for (auto child : node->children)
                    q.push(child);
            }
            cout << "\n";
            q.pop();
            if (!q.empty())
                q.push(marker);
        }
    }
}
int main() {
    vector<int> parent = {-1, 0, 3, 0, 6, 6, 3};
    Node *root = constructTree(parent);
    levelPrint(root);
    return 0;
}

复杂度分析

时间

每调用一次createNode生成一个节点，而createNode中没有什么循环之类的操作，所以，时间复杂度O(N)

空间

需要一个nodeP数组，所以空间复杂度是O(N)