(C卷,100分)- 悄悄话（Java & JS & Python & C）

题目描述

给定一个二叉树，每个节点上站一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。

初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。

输入描述

给定二叉树

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

注：-1表示空节点

输出描述

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

38

用例

题目解析

题目给的输入信息对照图示来看，应该就是二叉树的层序遍历序列，如下图所示：

层序遍历序列中，父子节点存在如下关系：

如果父节点在序列中的索引是k，则其两个子节点在序列中的索引分别为 2k+1, 2k+2

因此，我们就无需建树操作了。

而悄悄话的传递，其实父节点将自身得到消息的时延累加到其各个子节点上，最终叶子节点中最大的时延值就是：二叉树所有节点上的人都接收到悄悄话花费的时间

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const times = (await readline()).split(" ").map(Number);

  // 记录题解
  let ans = 0;

  // 根节点的索引是0
  const queue = [0];
  while (queue.length > 0) {
    const fa = queue.shift(); // 父节点索引

    const ch1 = 2 * fa + 1; // 左子节点索引
    const ch2 = 2 * fa + 2; // 右子节点索引

    // fa是否存在左子节点
    const ch1_exist = ch1 < times.length && times[ch1] != -1;
    // fa是否存在右子节点
    const ch2_exist = ch2 < times.length && times[ch2] != -1;

    // fa如果存在左子节点
    if (ch1_exist) {
      times[ch1] += times[fa];
      queue.push(ch1);
    }

    // fa如果存在右子节点
    if (ch2_exist) {
      times[ch2] += times[fa];
      queue.push(ch2);
    }

    // fa是叶子节点
    if (!ch1_exist && !ch2_exist) {
      // 保留叶子节点中最大时延
      ans = Math.max(ans, times[fa]);
    }
  }

  console.log(ans);
})();

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

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

    int[] times = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    // 记录题解
    int ans = 0;

    // 根节点的索引是0
    LinkedList<Integer> queue = new LinkedList<>();
    queue.addLast(0);

    while (queue.size() > 0) {
      int fa = queue.removeFirst(); // 父节点索引

      int ch1 = 2 * fa + 1; // 左子节点索引
      int ch2 = 2 * fa + 2; // 右子节点索引

      // fa是否存在左子节点
      boolean ch1_exist = ch1 < times.length && times[ch1] != -1;
      // fa是否存在右子节点
      boolean ch2_exist = ch2 < times.length && times[ch2] != -1;

      // fa如果存在左子节点
      if (ch1_exist) {
        times[ch1] += times[fa];
        queue.addLast(ch1);
      }

      // fa如果存在右子节点
      if (ch2_exist) {
        times[ch2] += times[fa];
        queue.addLast(ch2);
      }

      // fa是叶子节点
      if (!ch1_exist && !ch2_exist) {
        // 保留叶子节点中最大时延
        ans = Math.max(ans, times[fa]);
      }
    }

    System.out.println(ans);
  }
}

Python算法源码

# 输入获取
times = list(map(int, input().split()))


# 算法入口
def getResult():
    # 记录题解
    ans = 0

    # 根节点的索引是0
    queue = [0]
    while len(queue) > 0:
        fa = queue.pop(0)  # 父节点索引

        ch1 = 2 * fa + 1  # 左子节点索引
        ch2 = 2 * fa + 2  # 右子节点索引

        # fa是否存在左子节点
        ch1_exist = ch1 < len(times) and times[ch1] != -1
        # fa是否存在右子节点
        ch2_exist = ch2 < len(times) and times[ch2] != -1

        # fa如果存在左子节点
        if ch1_exist:
            times[ch1] += times[fa]
            queue.append(ch1)

        # fa如果存在右子节点
        if ch2_exist:
            times[ch2] += times[fa]
            queue.append(ch2)

        # fa是叶子节点
        if not ch1_exist and not ch2_exist:
            # 保留叶子节点中最大时延
            ans = max(ans, times[fa])

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX(a,b) ((a) > (b) ? (a) : (b))

#define MAX_SIZE 10000

typedef struct ListNode {
    int ele;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *listNode = (ListNode *) malloc(sizeof(ListNode));
    listNode->ele = ele;
    listNode->next = NULL;

    if(link->size == 0) {
        link->head = listNode;
        link->tail = listNode;
    } else {
        link->tail->next = listNode;
        link->tail = listNode;
    }

    link->size++;
}

int removeFirst_LinkedList(LinkedList* link) {
    if(link->size == 0) exit(-1);

    ListNode* removed = link->head;

    if(link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
    }

    link->size--;

    int res = removed->ele;

    free(removed);

    return res;
}

int main() {
    int times[MAX_SIZE];
    int times_size = 0;

    while (scanf("%d", &times[times_size++])) {
        if(getchar() != ' ') break;
    }

    // 记录题解
    int ans = 0;

    // 根节点的索引是0
    LinkedList* queue = new_LinkedList();
    addLast_LinkedList(queue, 0);

    while (queue->size > 0) {
        int fa = removeFirst_LinkedList(queue); // 父节点索引

        int ch1 = 2 * fa + 1; // 左子节点索引
        int ch2 = 2 * fa + 2; // 右子节点索引

        // fa是否存在左子节点
        int ch1_exist = ch1 < times_size && times[ch1] != -1;
        // fa是否存在右子节点
        int ch2_exist = ch2 < times_size && times[ch2] != -1;

        // fa如果存在左子节点
        if(ch1_exist) {
            times[ch1] += times[fa];
            addLast_LinkedList(queue, ch1);
        }

        // fa如果存在右子节点
        if(ch2_exist) {
            times[ch2] += times[fa];
            addLast_LinkedList(queue, ch2);
        }

        // fa是叶子节点
        if(!ch1_exist && !ch2_exist) {
            // 保留叶子节点中最大时延
            ans = MAX(ans, times[fa]);
        }
    }

    printf("%dn", ans);

    return 0;
}