一道完全二叉树的算法题

Question

已知一棵最大深度为16的完全二叉树，所有叶子节点的深度相同。如果在根节点放置一个小球，球将开始沿着根节点下落。完全二叉树的每个节点上都有一个开关。默认是全部关闭。当球落下时，只要球落在开关上，开关的状态就会发生变化。当小球到达一个节点时，如果该节点上的开关是闭合的，就往左走去接小球，否则往右走，直到到达叶节点。请帮我求出第12345个球落下后的叶节点编号

Answer 1

您可以模拟给定的问题，并注意到球结束的叶节点往往会在某个时间点后自行重复。例如，对于深度为3的二叉树，多次滚动球结束的叶子节点是1 3 2 4 1 3 2 4 1 3 2 4 . . .（假设叶子节点从1开始编号).可见，长度为 2^3-1 = 4 的序列不断重复。我们可以将这个序列存储在一个数组中，并通过查找对应于 n mod 2[= 的条目来回答对任何 n^th 投球的查询23=]depth-1 数组中的索引。

由于我们的深度达到 16，因此生成循环序列所需的操作总数为 2^16-1 * 16 = 524288 操作。

共享相同的代码https://ideone.com/uuNV2g

#include <iostream>
#include <map>
#include <vector>
using namespace std;

map<int, bool> states; // default value is False
int MAX_DEPTH = 16;

int dfs(int cur, int depth = 0) {
    if(depth == MAX_DEPTH) {
        return cur - (1<<MAX_DEPTH) + 1;
    }

    if(states[cur] == 0) {
        states[cur] = !states[cur];
        return dfs(2*cur, depth+1);
    }
    else {
        states[cur] = !states[cur];
        return dfs(2*cur+1, depth+1);
    }

}

int main() {
    int until = (1LL<<(MAX_DEPTH-1));
    vector<int> pos; // 0 indexed
    for(int i = 1; i <= until; i++) {
        // cout << dfs(1) << ' ';
        pos.push_back(dfs(1));
    }

    cout << pos[(12344%until)]; 
    // 12344 instead of 12345 since the sequence is 0 indexed
}

希望一切顺利。

一道完全二叉树的算法题

A algorithm problem of complete two binary tree

algorithm

binary-tree