【2024华为OD机试真题C卷D卷-100分】悄悄话花费的时间【C++/Java/Python】_二叉树传递悄悄话

2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++)

题目描述

给定一个二叉树，每个节点上站着一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。

输入描述

给定二叉树

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

注：-1 表示空节点

输出描述

返回所有节点都接收到悄悄话花费的时间 38

示例一

输入

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

输出

38

考点

二叉树层序遍历

 

解题思路：

构建二叉树：首先，根据题目给出的输入数组（层序遍历顺序），通过递归函数构建一棵完全二叉树。在函数中，当遇到非空节点时（数组值不为-1），创建一个新节点并将其值设置为数组中的当前元素，然后递归地构建其左、右子节点。

计算传递时间总和：定义一个递归函数来计算以给定节点为根的二叉树中所有节点接收悄悄话所需的时间总和。

当遍历到空节点时，返回0，表示没有额外的传递时间；

对于非空节点，首先递归计算左子树和右子树的最大传递时间；

将当前节点的值与左右子树中的较大传递时间相加，得到从当前节点开始向下传递悄悄话所需的时间；

最终，根节点下的时间总和即为整个二叉树所有节点接收到悄悄话的总时间。

代码 

c++

#include <bits/stdc++.h>
using namespace std;
 
typedef struct Node_{
    int val;
    struct Node_* left;
    struct Node_* right;
    Node_(int v) {
        val=v;
        left=NULL;
        right=NULL;
    }
}Node;
 
int get_time(Node* root) {
    if(root==NULL) {
        return 0;
    }
    int l=get_time(root->left);
    int r=get_time(root->right);
    return root->val+max(l,r);
}
 
int main() {
    int tmp;
    vector<int> vec;
    vector<Node*> nodes;
    while(cin>>tmp) {
        vec.push_back(tmp);
        if(cin.get()=='\n') break;
    }
    int n=vec.size();
    for(int i=0;