解答と解説: Identical Binary Trees

「問題演習: Identical Binary Trees」の解答編です。再帰と深さ優先探索を用いた解答例を示します。

解答例

Javaでの解答例です。

解答例１）

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class IdenticalBinaryTree {
	public boolean isIdentical(Node n1, Node n2) {
	if (n1 == null && n2 == null) {
	return true;
	}
	if (n1 == null || n2 == null) {
	return false;
	}
	if (n1.value != n2.value) {
	return false;
	}
	return isIdentical(n1.left, n2.left) && isIdentical(n1.right, n2.right);
	}
	}

view raw identical-binary-tree.java hosted with ❤ by GitHub

解答例２）

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class IdenticalBinaryTree {
	public boolean isIdentical(Node n1, Node n2) {
	Stack<Node> stack1 = new Stack<>();
	Stack<Node> stack2 = new Stack<>();
	if (n1 == null && n2 == null) {
	return true;
	}
	if (n1 == null || n2 == null) {
	return false;
	}
	stack1.push(n1);
	stack2.push(n2);
	while (!stack1.isEmpty() && !stack2.isEmpty()) {
	Node a = stack1.pop();
	Node b = stack2.pop();
	if (a.value != b.value) {
	return false;
	}
	if (a.left == null && b.left == null) {
	// Do nothing
	} else if (a.left == null || b.left == null) {
	return false;
	} else {
	stack1.push(a.left);
	stack2.push(b.left);
	}
	if (a.right == null && b.right == null) {
	// Do nothing
	} else if (a.right == null || b.right == null) {
	return false;
	} else {
	stack1.push(a.right);
	stack2.push(b.right);
	}
	}
	return true;
	}
	}

view raw identical-binary-tree.java hosted with ❤ by GitHub

解説

解答例１は再帰を使い、解答例２は深さ優先探索を使った解法です。

解答例１の再帰を使った解法では、現在のノード n1 と n2 が等しい場合は左右の子要素についても isIdentical() メソッドを呼び出すことで、全てのノードが等しいか調べることができます。解答例２では、2 つのスタックを用いて同時に木構造を下降し、各ノードで 2 つのノードが等しいか調べています。

この問題では再帰を使った方がコードが短く、バグが入り込みにくいのでオススメです。ただし、「解答と解説: Max Depth of Binary Tree」でも述べましたが、木の高さが非常に高いと再帰関数（メソッド）呼び出し回数が多くなり、StackOverflowError を引き起こす可能性があります。そのような場合はループを用いて探索を行う必要があります。 問題にメモリ使用量の制約などがある場合は注意しましょう。

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