解答と解説: Symmetric Binary Tree

「問題演習: Symmetric Binary Tree」の解答編です。今回は再帰を用いた解答例と深さ優先探索を用いた解答例の 2 つを用意しました。

解答例

Javaでの解答例です。

解答例１）再帰

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public boolean isSymmetric(Node root) {
	if (root == null) {
	return true;
	}
	return helper(root.left, root.right);
	}
	private boolean helper(Node left, Node right) {
	if (left == null && right == null) {
	return true;
	}
	if (left == null || right == null) {
	return false;
	}
	if (left.value != right.value) {
	return false;
	}
	return helper(left.left, right.right) && helper(left.right, right.left);
	}
	}

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

解答例２）深さ優先探索

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public boolean isSymmetric(Node root) {
	Stack<Node> stack1 = new Stack<>();
	Stack<Node> stack2 = new Stack<>();
	if (root != null) {
	stack1.push(root);
	stack2.push(root);
	}
	while (!stack1.isEmpty() && !stack2.isEmpty()) {
	Node n1 = stack1.pop();
	Node n2 = stack2.pop();
	if (n1.value != n2.value) {
	return false;
	}
	if (n1.left != null) {
	if (n2.right == null) {
	return false;
	}
	stack1.push(n1.left);
	stack2.push(n2.right);
	} else if (n2.right != null) {
	return false;
	}
	if (n1.right != null) {
	if (n2.left == null) {
	return false;
	}
	stack1.push(n1.right);
	stack2.push(n2.left);
	} else if (n2.left != null) {
	return false;
	}
	}
	return true;
	}
	}

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

解説

この問題では両端の枝を根から葉まで下降する際に、枝上の各ノードを順に比較する方法がイメージできると解きやすいと思います。

解答例１では、helper 関数内で 2 つのノードの比較を行い、値が異なった場合は左右対称でないと判断して false を返します。値が同じだった場合は、左ノードの左の子と右のノードの右の子を helper 関数に渡すことによって、両端の枝を下降していることがわかります。そして左ノードの右の子と右のノードの左の子の比較を行えば、1 つ内側の枝を下降するができ、これを繰り返し行うことで全ての枝上にあるノードの左右対称性を調べることができます。

解答例２では、スタックを 2 つ使って深さ優先探索を左右から同時に行っています。各ノードに辿り着く度にノードの値を比較しています。ポイントとしては、子要素をスタックに積むとき、片方のスタックに左の子要素を積んだ場合はもう一方には右の子要素を入れることがです。左右が逆の場合も同様です。このようにすることで、両端のノードから順に左右対称性を調べることができます。

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