题目链接

分布式系统任务调度

题目描述

在一个二叉树结构的分布式计算系统中，需要找到任意两个节点 和 的层级最低的共同主控节点（即最近公共祖先 LCA），并返回该主控节点所管辖的节点总数（不包括主控节点自身）。

输入:

  • 第一行一个整数 ，表示二叉树的节点总数。
  • 第二行 个整数，表示二叉树的层序遍历序列，其中 代表空节点。
  • 第三行两个整数 和 ，表示待查询的两个节点的 ID。

输出:

  • 一个整数，表示 和 的最近公共祖先的子树大小（不含其自身）。

解题思路

该问题的核心是找到二叉树中两个节点的最近公共祖先（LCA），并计算其子树的大小。一个非常高效的方法是利用层序遍历序列的数组表示特性，避免显式地构建树。

假设层序遍历序列存储在一个从 1 开始索引的数组中，那么对于任意索引为 的节点：

  • 它的父节点索引为 。
  • 它的左子节点索引为 。
  • 它的右子节点索引为 。

基于此，解题步骤如下：

  1. 数据预处理

    • 将输入的层序遍历序列存入一个从索引 1 开始的数组 。
    • 创建一个哈希表（map） ，用于存储每个节点值到其在数组 中索引的映射，即 。这可以让我们快速通过节点值定位其位置。

  2. 计算所有子树的大小

    • 创建一个数组 来存储每个位置对应节点的子树大小。
    • 从后向前遍历数组 （从索引 到 ）。对于每个非空节点（值不为 ）：
      • 将当前位置 的子树大小 加上 1（代表节点自身）。
      • 将其子树大小贡献给父节点，即 。
    • 由于是从叶子节点开始向上处理，当处理到一个父节点时，其所有子节点的子树大小已经计算完毕，所以这种自底向上的累加可以正确计算出每个节点的子树总大小。

  3. 查找最近公共祖E (LCA)

    • 使用哈希表 找到待查询的两个节点值 和 对应的数组索引 和 。
    • 使用一个循环来寻找它们的LCA。在每次循环中，将索引值较大的节点移动到其父节点（即 ）。
    • 当两个索引 和 相等时，该索引即为LCA节点的索引。

  4. 输出结果

    • LCA 节点的索引为 。从预处理好的数组 中取出其子树大小 。
    • 根据题目要求，输出不包含主控节点自身的节点总数，即 。

代码

#include <iostream>
#include <vector>
#include <map>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<ll> a(n + 1);
    map<ll, int> b;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] != -1) {
            b[a[i]] = i;
        }
    }

    vector<int> c(n + 1, 0);
    for (int i = n; i >= 1; --i) {
        if (a[i] != -1) {
            c[i] += 1; // 节点自身
            if (i / 2 > 0) {
                c[i / 2] += c[i]; // 累加到父节点
            }
        }
    }

    ll u_val, v_val;
    cin >> u_val >> v_val;

    int u_idx = b[u_val];
    int v_idx = b[v_val];

    // 寻找LCA
    while (u_idx != v_idx) {
        if (u_idx > v_idx) {
            u_idx /= 2;
        } else {
            v_idx /= 2;
        }
    }

    cout << c[u_idx] - 1 << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long[] a = new long[n + 1];
        Map<Long, Integer> b = new TreeMap<>();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
            if (a[i] != -1) {
                b.put(a[i], i);
            }
        }

        int[] c = new int[n + 1];
        for (int i = n; i >= 1; i--) {
            if (a[i] != -1) {
                c[i] += 1; // 节点自身
                if (i / 2 > 0) {
                    c[i / 2] += c[i]; // 累加到父节点
                }
            }
        }

        long uVal = sc.nextLong();
        long vVal = sc.nextLong();

        int uIdx = b.get(uVal);
        int vIdx = b.get(vVal);

        // 寻找LCA
        while (uIdx != vIdx) {
            if (uIdx > vIdx) {
                uIdx /= 2;
            } else {
                vIdx /= 2;
            }
        }

        System.out.println(c[uIdx] - 1);
    }
}

import sys

def main():
    # 读取输入
    n = int(input())
    
    if n == 0:
        print(0)
        return

    a_vals = list(map(int, input().split()))
    u_val, v_val = map(int, input().split())

    a = [0] * (n + 1)
    b = {}
    for i in range(n):
        a[i + 1] = a_vals[i]
        if a_vals[i] != -1:
            b[a_vals[i]] = i + 1

    c = [0] * (n + 1)
    for i in range(n, 0, -1):
        if a[i] != -1:
            c[i] += 1  # 节点自身
            if i // 2 > 0:
                c[i // 2] += c[i]  # 累加到父节点

    u_idx = b[u_val]
    v_idx = b[v_val]

    # 寻找LCA
    while u_idx != v_idx:
        if u_idx > v_idx:
            u_idx //= 2
        else:
            v_idx //= 2
    
    print(c[u_idx] - 1)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：数组模拟树 + 动态规划
  • 时间复杂度：，其中 是节点总数。输入和预计算子树大小都需要 的时间。查找LCA的过程时间复杂度为 ，因此总时间复杂度为 。
  • 空间复杂度：，用于存储节点数组、值到索引的映射以及子树大小的数组。