BT to Array

Given a tree, try to implemnt it using other data structures to reduce the overhead.

pointer: 4bytes(32bit computing)/8bytes(64bit computing)

先求深度，然后用2的深度次方获得数组的长度。BFS把每个node都塞到数组里面。

存树。用什么办法可以节省空间，如果比较full的tree，用heap的实现方式。比较sparse的tree就用tree本身。介于中间的可以用两个数组，一个表示value，一个表示这个节点在第一种表示方式下的index(---->hashmap)。

https://instant.1point3acres.com/thread/159113
compressDenseTree

compressSparseTree

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;
class TreeNode {
public:
    int id;
    TreeNode *left, *right;
    TreeNode(int id) : id(id), left(nullptr), right(nullptr){}
};
int getH(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(getH(root->left), getH(root->right));
}
void DFS(TreeNode* root, int idx, vector<int>& res) {
    if (!root) return;
    res[idx] = root->id;
    DFS(root->left, idx*2, res);
    DFS(root->right, idx*2+1, res);
}
void compressDenseTree(TreeNode* root) {
    int height = getH(root);
    vector<int> res(1 << height, -1) ;
    DFS(root, 1, res);
    cout<<"compressDenseTree:"<<endl;
    for (int i = 0; i < res.size(); i++)
        cout<<i<<' '<<res[i]<<endl;
}
void compressSparseTree(TreeNode* root) {
    if (!root) return;
    unordered_map<int, int> res; //idx to id
    queue<pair<int, TreeNode*>> toVisit;    //idx and node
    toVisit.emplace(1, root);
    res[1] = root->id;
    while (!toVisit.empty()) {
        int idx = toVisit.front().first;
        TreeNode *curr = toVisit.front().second;
        toVisit.pop();
        if (!curr) continue;
        res[idx] = curr->id;
        toVisit.emplace(idx*2, curr->left);
        toVisit.emplace(idx*2+1, curr->right);

    }

    cout<<"compressSparseTree:"<<endl;
    for (auto kv : res)
        cout<<kv.first<<' '<<kv.second<<endl;
}
int main(int argc, char *argv[]) {
    //for pratice, i used recursive DFS for dense tree, and BFS for sparse tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->right = new TreeNode(7);
    root->left->left->left = new TreeNode(8);
    root->left->left->left = new TreeNode(9);
    compressDenseTree(root);
    compressSparseTree(root);
}