解答と解説: Average of each Level in Binary Tree

「問題演習: Average of each Level in Binary Tree」の解答編です。問題出題時に述べたように、この問題は本サイトに掲載してきた 2 分木に関する問題「Max Depth of Binary Tree」や「Find Max Element per Level in Binary Tree」と似ており、解答も非常に似ています。そのため、解答例の細かい解説はそちらの記事を見ていただきたいと思います。今回の解説では問題出題時の最後に記載した "もし数値の 1 つが int 型の最大値だった場合" について解法を紹介したいと思います。

解答例

Javaでの解答例です。

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public List<Double> findAverages(Node root) {
	List<Double> list = new ArrayList<>();
	Queue<Node> q = new LinkedList<>();
	if (root != null) {
	q.offer(root);
	}
	while (!q.isEmpty()) {
	int size = q.size();
	double sum = 0;
	for (int i = 0; i < size; i++) {
	Node n = q.poll();
	sum += ((double) n.value) / size;
	if (n.left != null) {
	q.offer(n.left);
	}
	if (n.right != null) {
	q.offer(n.right);
	}
	}
	list.add(sum);
	}
	return list;
	}
	}

view raw average-of-each-level-in-binary-tree.java hosted with ❤ by GitHub

解説

もし数値の 1 つが int 型の最大値だった場合、1 を足しただけでも int 型の範囲を超えてしまうことによって符号が反転し、負の整数になってしまいます。具体的な数値は下記になります。

• Integer.MAX_VALUE = 2147483647
• Integer.MAX_VALUE + 1 = -2147483648

今回の問題では、複数の値の平均値を求めるために、複数の数値の和を数値の数で割ろうとしていました。しかし数値に int 型の最大値が含まれていた場合、単純に和を求めようとしても、期待した結果が得ることはできません。

解法は解答例の 20 行目で示したように、全ての和を求めてから割り算するのではなく、各数値を 1 つずつ足していく際に数値の数で割っています。あらかじめ数値の数が分かっているので、このような処理を行うことができます。非常に単純なことですが、実際の面接ではこのような処理を瞬時に思いつくことができなくてはならないので、今回この問題を取り上げました。

以上が今回の解説になります。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。