問題演習: Average of each Level in Binary Tree

今回は「Average of each Level in Binary Tree」という問題です。この問題はこれまでに本サイトに掲載してきた 2 分木に関する問題「Max Depth of Binary Tree」や「Find Max Element per Level in Binary Tree」と似ているので掲載するか迷ったのですが、1 点だけ注意してほしいことがあったので掲載することにしました。その注意して欲しい点は下記の「解答を見る前に」に記載したので考えてみてください。難易度は「Easy」です。

問題

各ノードに整数値を持つ 2 分木が与えられる。2 分木の深さごとの平均値を求め、リストに入れて返せ。

解答テンプレート

Javaの例を示します。

入出力例

次の 2 分岐が与えられるとする。このとき返すリストは [1, 2.5, 11] である。

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

解答を見る前に

平均値を求めるとき、数値の和を数値の数で割ります。もし数値の 1 つが int 型の最大値だった場合、1 を足すだけでもオーバーフローを起こし、意図した計算結果が得られません。このような場合、どのような処理をして平均値を求めれば良いでしょうか。

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