深度优先搜索 - 塔子哥的完整二叉树

一、问题分析

• 给定一棵 完整二叉树，每个节点要么 没有子节点（叶子），要么 有两个子节点（非叶子）。
• 叶子节点的权值为 1。
• 非叶子节点的权值 由其 左右子节点的权值 计算：
  • c[i] = 0 → 加法：权值 = 左子权值 + 右子权值
  • c[i] = 1 → 乘法：权值 = 左子权值 × 右子权值
• 求 根节点的权值，结果取 模 $10^9 + 7$。

二、解题思路

1. 存储树结构

• 题目输入提供的是 父节点列表，可以 构建邻接表 存储子节点：
  • 用 adj[u] 记录 节点 u 的子节点。
  • 叶子节点 没有子节点，非叶子节点 必定有 2 个子节点。

2. 递归计算权值（DFS）

• 递归遍历 整棵树：
  • 如果是叶子节点，返回 1。
  • 如果是非叶子节点：
    1. 递归计算 左子树的权值 left_val。
    2. 递归计算 右子树的权值 right_val。
    3. 根据 运算类型 c[u] 计算 权值 = left_val + right_val（加法）或 left_val × right_val（乘法）。
    4. 结果取模 $10^9 + 7$ 避免溢出。

3. 计算根节点的权值

• 调用 cal(0)（根节点编号 从 0 开始）。
• 输出计算结果。

4. 复杂度分析

• 构建邻接表： O(n)
• DFS 遍历所有节点： O(n)
• 总时间复杂度： O(n)

三、代码实现

具体实现参考以下代码：

Python

MOD = 10**9 + 7

def cc(a, b, t):
    """ 根据运算类型 t 计算当前节点的权值 """
    return (a + b) % MOD if t == 0 else (a * b) % MOD

def cal(u):
    """ 递归计算节点 u 的权值 """
    if len(adj[u]) == 2:  # 非叶子节点，递归计算左右子节点的值
        return cc(cal(adj[u][0]), cal(adj[u][1]), ops[u])
    return 1  # 叶子节点权值固定为 1

# 读取输入
num = int(input().strip())
tree_info = list(map(int, input().split()))
ops = list(map(int, input().split()))

# 构建邻接表
adj = [[] for _ in range(num)]
for i in range(num - 1):
    parent = tree_info[i] - 1  # 转换为 0 索引
    child = i + 1
    adj[parent].append(child)

# 输出根节点的计算结果
print(cal(0))

Java

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    static List<Integer>[] adj; // 邻接表
    static int[] ops; // 运算类型数组

    // 计算节点值
    static long cc(long a, long b, int t) {
        return (t == 0) ? (a + b) % MOD : (a * b) % MOD;
    }

    // 递归计算节点 u 的权值
    static long cal(int u) {
        if (adj[u].size() == 2) {
            return cc(cal(adj[u].get(0)), cal(adj[u].get(1)), ops[u]);
        }
        return 1; // 叶子节点权值固定为 1
    }

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

        adj = new ArrayList[num];
        ops = new int[num];

        for (int i = 0; i < num; i++) {
            adj[i] = new ArrayList<>();
        }

        // 读取父子关系
        for (int i = 1; i < num; i++) {
            int parent = sc.nextInt();
            adj[parent - 1].add(i);
        }

        // 读取运算类型
        for (int i = 0; i < num; i++) {
            ops[i] = sc.nextInt();
        }

        // 计算并输出根节点权值
        System.out.println(cal(0));
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;
const int MOD = 1e9 + 7;

vector<vector<int>> adj; // 邻接表存储树结构
vector<int> ops;         // 运算类型数组

// 计算节点值
long long cc(long long a, long long b, int t) {
    return (t == 0) ? (a + b) % MOD : (a * b) % MOD;
}

// 递归计算节点 u 的权值
long long cal(int u) {
    if (adj[u].size() == 2) {
        return cc(cal(adj[u][0]), cal(adj[u][1]), ops[u]);
    }
    return 1; // 叶子节点权值固定为 1
}

int main() {
    int num;
    cin >> num;

    adj.resize(num);
    ops.resize(num);

    // 读取父子关系
    for (int i = 1; i < num; i++) {
        int parent;
        cin >> parent;
        adj[parent - 1].push_back(i);
    }

    // 读取运算类型
    for (int i = 0; i < num; i++) {
        cin >> ops[i];
    }

    // 计算并输出根节点权值
    cout << cal(0) << endl;

    return 0;
}

本题为2023年9月8日百度机考原题

百度机考的介绍点击这里

题目描述

塔子哥有一棵节点数为 $n$ 的完整二叉树，对于一个完整二叉树的定义是：要么每个节点有两个子节点，要么每个节点没有子节点。

• 没有子节点的节点，其权值为 $1$ 。
• 有两个子节点的节点，其权值为两个儿子节点的权值的运算结果。

每个节点有两种运算，要么为加法，要么为乘法。如下给出一个长度为 $n$ 的数组 $c$ 。

$c_i=0$ 表示节点 $i$ 的运算是加法，$c_i=1$ 表示节点 $i$ 的运算是乘法。

现在，塔子哥问你这个完整二叉树的根节点的权值是多少。

输入描述

第一行，一个正整数 $n(1\leq n\leq 10^5)$ 表示完整二叉树中的节点个数。

第二行，$n-1$ 个正整数 $p[2,3,...,n]$，$p[i](1\leq p[i]\leq n)$ 表示第 $i$ 个节点的父节点，$1$ 号节点是根节点。

第三行，$n$ 个整数 $c[1,2,...,n]$ ，含义如题面描述所示

数据保证形成满足题目描述的二叉完整树。

输出描述

一个整数，表示根节点的值，答案对 $10^9+7$ 取模。

样例

输入

3
1 1
1 1 1

输出

1

说明

$2$ 号节点和 $3$ 号节点权值均为 $1$ ，$1$ 号节点是乘法运算，故 $1$ 号节点的权值为 $1$ 。