缺损二叉树

题目

by 庾湫镆

描述

有一棵满二叉树, 按层序依次编号为 1 .... 现指定一部分编号, 当层序遍历到这些编号时, 它们的子孙结点将不会加入遍历. 在这种情况下, 求从根节点到目标编号结点的路径.

IO格式

输入:

指定编号数 目标编号数
指定编号...     // 从小到大
目标编号...     // 从小到大

输出:

路径
...

样例

输入:

3 4
5 6 9
3 9 15 22

输出:

1 3 
1 2 4 9 
1 3 7 10 15 
1 3 7 10 14 22

解答

思路

当一个结点前面出现了 absentNum 个指定编号结点的子树, 它与其父节点之间的编号关系 (father = son >> 1) 将会偏移 absentNum. 只要我们求出 absentNum 对应的结点编号区间 absentRanges[absentNum], 就能轻松解决这道题.

代码

#include <array>
#include <cstdio>
#include <stack>
using namespace std;

#define prf printf
#define scf scanf
using ui = unsigned long long;

ui N;                            // 缺损点数目
ui M;                            // 目标点数目
array<ui, 102> absentNodes;      // 缺损点, [0]空余
array<ui, 102> absentRanges{1};  // 缺损连续区间, 0表示不存在

ui findLeftSon(ui father, ui absentNum) { return (father - absentNum) << 1; }

ui findFather(ui son, ui absentNum) { return (son >> 1) + absentNum; }

ui findRange(ui target) {
    for (auto i = N; i >= 0; i--)
        if (absentRanges[i] != 0)
            if (absentRanges[i] <= target) return i;
}

int main() {
    scf("%u%u", &N, &M);
    for (auto i = 1; i <= N; i++) {
        ui temp;
        scf("%u", &temp);
        absentNodes[i] = temp;
        absentRanges[i] = findLeftSon(temp, i - 1);
        if (absentRanges[i] == absentRanges[i - 1]) absentRanges[i - 1] = 0;
    }
    for (auto i = 0; i < M; i++) {
        ui temp;
        scf("%u", &temp);
        stack<ui> path;
        path.push(temp);
        ui pathLen = 1;
        auto flag = false;
        while (temp != 1) {
            auto tempFather = findFather(temp, findRange(temp));
            if (tempFather >= temp) {
                flag = true;
                break;
            }
            temp = tempFather;
            path.push(temp);
            pathLen++;
        }
        if (flag) {
            prf("0\n");
            continue;
        } else {
            for (auto j = 0; j < pathLen; j++) {
                prf("%u ", path.top());
                path.pop();
            };
            prf("\n");
        }
    }
    return 0;
}

时空消耗

1	Accepted	0 ms	920 KB
2	Accepted	0 ms	916 KB
3	Accepted	0 ms	924 KB
4	Accepted	0 ms	916 KB
5	Accepted	0 ms	916 KB
6	Accepted	0 ms	920 KB
7	Accepted	0 ms	916 KB
8	Accepted	0 ms	916 KB
9	Accepted	0 ms	924 KB
10	Accepted	0 ms	920 KB