解答と解説: Max Depth of Binary Tree

「問題演習: Max Depth of Binary Tree」の解答編です。2 通りの解答例を用意しました。それぞれの解法について解説します。

解答例

Javaでの解答例です。

１）再帰

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public int maxDepth(Node root) {
	return maxDepthHelper(root);
	}
	public int maxDepthHelper(Node node) {
	if (node == null) {
	return 0;
	}
	return Math.max(maxDepthHelper(node.left), maxDepthHelper(node.right)) + 1;
	}
	}

view raw max-depth.java hosted with ❤ by GitHub

２）幅優先探索

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public int maxDepth(Node root) {
	if (root == null) {
	return 0;
	}
	int count = 0;
	Queue<Node> q = new LinkedList<>();
	q.offer(root);
	while (!q.isEmpty()) {
	int size = q.size();
	for (int i = 0; i < size; i++) {
	Node n = q.poll();
	if (n.left != null) {
	q.offer(n.left);
	}
	if (n.right != null) {
	q.offer(n.right);
	}
	}
	count++;
	}
	return count;
	}
	}

view raw max-depth.java hosted with ❤ by GitHub

解説

再帰を用いた解法は、コードの記述量が少なくエラーが混入しにくいので、問題に特に制約が付いていない場合はお薦めの解答です。しかし再帰が使えない場面では幅優先探索の解法がおすすめです。どのような場面で再帰が使えないかわかりますか？

関数（メソッド）呼び出しをアセンブラ・レベルで見ると、引数や戻り先のアドレスがスタック（メモリ）に積まれます。この処理は関数呼び出しの度に行われるため、際限なく何度も関数を呼び出すとスタックの使用可能量を超えてメモリを確保しようとしてしまいます。このとき、例えば Java では StackOverflowError を引き起こし、プログラムが強制終了してしまいます。つまり木の高さが非常に高く、使用可能なメモリの量が少ない場合は StackOverflowError を引き起こす可能性があります。

この事態を避けるために、幅優先探索での解法が有効です。この解法では何度も関数を呼び出す必要がないため、スタックが溢れることはありません。

この問題が実際に面接で出題された場合でも、再帰が使えない場面について質問されるかはわかりません。もし質問された場合は、上記のように理由と対処法について言及できれば良い評価を得られるでしょう。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。