解答と解説: Find Max Element per Level in Binary Tree

「問題演習: Find Max Element per Level in Binary Tree」の解答編です。

解答例

Javaでの解答例です。

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public List<Integer> maxElementPerLevel(Node root) {
	List<Integer> list = new ArrayList<>();
	Queue<Node> q = new LinkedList<>();
	if (root != null) {
	q.offer(root);
	}
	while (!q.isEmpty()) {
	int largest = Integer.MIN_VALUE;
	int size = q.size();
	for (int i = 0; i < size; i++) {
	Node node = q.poll();
	largest = Math.max(largest, node.value);
	if (node.left != null) {
	q.offer(node.left);
	}
	if (node.right != null) {
	q.offer(node.right);
	}
	}
	list.add(largest);
	}
	return list;
	}
	}

view raw find-max-element-per-level-in-binary.java hosted with ❤ by GitHub

解説

高さごとの最大値を求める問題なので、同じ高さのノードから順に走査を行う幅優先探索を用いています。以下に解答例での注意点について述べます。

11 行目で Queue インタフェースを実装した LinkedList クラスのインスタンス化を行います。Queue は offer メソッドで要素の追加を行い、poll メソッドで削除と取得を行います。List では add と remove、Stack では push と pop ですので混同しないようにしましょう。

12, 13 行目で root が null でない場合に Queue に追加した後、15 行目からの while 文で Queue の要素がなくなるまでループします。このループ内部の操作は主に次の 2 つの操作に分類できます。

• 同じ高さの要素を取り出し、最大値を見つける。
• 同じ高さの要素の左右の子を Queue に追加する。

Queue には次々に要素が追加されていくため、どの要素が同じ高さの要素なのかを区別する必要があります。そこで for ループに入る前の 17 行目で Queue のサイズを取得しています。この値が左右の子要素が追加される前の Queue のサイズ、つまり同じ高さの要素の数になります。このサイズを 18 行目の for ループの終了条件 "i < size" としていますが、"i < q.size()" としない理由は for ループ内で Queue に要素が追加され、子要素も含めたサイズになってしまうからです。


この問題は、前回の「解答と解説: Max depth of binary tree」で示した幅優先探索を用いた解答と非常によく似ています。Queue を Stack に置き換えることによって深さ優先探索のプログラムになります。非常に便利はパターンなので覚えてしまいましょう。

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