解答と解説: Invert a Binary Tree

「問題演習: Invert a Binary Tree」の解答編です。

解答例

Javaでの解答例です。

解説

ルートノードの位置は変わらず、左右の子ノードを入れ替える問題です。同様の処理を葉ノードまで実行すれば良いです。つまり再帰を使うと簡単に解けます。

最初に与えられるルートノードが null の可能性があるので、初めに調べておきます。ここで null チェックをしているので、その後 solve メソッドを呼ぶ前に null をチェックする必要はありません。solve メソッドに子ノードを投げてしまいましょう。余計なコードを減らすことで間違いが混入する可能性を減らすことも大事です。

この問題で一番大事なのは、余計なメモリを使用しないことです。例えば、新しい木構造を作る際に各ノードを複製し、最終的に木が 2 つできてしまう解法は好ましくないです。特に IT 企業の場合は、余計なメモリを使用することで処理が遅くなり、それが計算コストを高くすることで出費が多くなります。そのような無駄なコストは避けたいので、不要なメモリの利用や余計な計算はしないように工夫しましょう。

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