传递悄悄话

更多关于刷题的内容欢迎订阅我的专栏华为刷题笔记

题目描述：

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

输入描述：

给定二叉树

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

注：-1表示空节点

输出描述：

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

38

示例1

输入：

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

输出：

38

题解

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

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

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

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

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

源码

public class Secret {

	static Input input;
	static {
		input = new Input("0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2\n");
	}

	public static void main(String[] args) {
		String[] strings = input.nextLine().split(" ");
		int[] nodes = new int[strings.length];
		for (int i = 0; i < strings.length; i++) {
			nodes[i] = Integer.parseInt(strings[i]);
		}

		int time = getTime(nodes, 0);

		System.out.println(time);
	}

	public static int getTime(int[] nodes, int index) {
		if (index >= nodes.length) {
			return 0;
		}
		int left = getTime(nodes, index * 2 + 1);
		int right = getTime(nodes, index * 2 + 2);
		int max = Math.max(left, right);
		if (index == 0) {
			return max;
		}
		return nodes[index] + max;
	}
}