LeetCode: Binary Tree-3
Solve Tree Problems Recursively
ツリーの問題は、トップダウンもしくはボトムアップで再帰的に解くことができる。 トップダウンのアプローチでは、最初に探索したノードの子ノードを再帰的に探索する。つまり、このようなやり方になる。
- 対象ノードが空のノードである場合は終了
- 返り値を対象ノードの値で更新する
- 左の子ノードに対して同じ関数を適用し、返り値を取得する
- 右の子ノードに対して同じ関数を適用し、返り値を取得する
- 返り値に3と4の結果を追加し、返り値を返す
例えば、与えられた二分木の深さを知るためには、次のようなやり方で解く。 まず、ルートノードの深さは1である。ノードの深さがわかっていれば、その子ノードの深さもわかる。なので、再帰的に解くとき、親ノードの深さをパラメーターとして渡せば、子ノードの深さもわかり、またその子ノードの深さを知ることができる。深さを知るための関数maximum_depth(root, depth)は以下のような動きをする。
- rootが空ならここで終わる
- もしrootが空でなければ
- answer = このノードの深さとanswerの深い方
- maximum_depth(root.left, depth + 1)
- maximum_depth(root.right, depth + 1)
ボトムアップのアプローチでは、まず最初にすべての子ノードに対して再帰的に関数を呼び出す。そして返り値と対象ノードの値を比較して答えを導く。つまり、このようなやり方になる。 1. 対象ノードが空のノードである場合は終了 2. 左の子ノードに対して同じ関数を適用し、返り値を取得する 3. 右の子ノードに対して同じ関数を適用し、返り値を取得する 4. 2,3の結果と対象ノードの値から答えを導き、返す
ツリーの深さを知るときには、先程のトップダウンのアプローチとまた違った考え方もできる。左の子ノードからはじまるサブツリーと右の子ノードからはじまるサブツリーの深さがわかっていれば、対象ノードの深さはわかる。これを順々に適用することによって、ツリー全体の深さが得られる。深さを知るための関数maximum_depth(root)は以下のような動きをする。
- 対象ノードが空なら0を返す
- left_depth = maximum_depth(root.left)
- right_depth = maximum_depth(root.right)
- 2と3の深さの大きいほうに1を足した値を返す
結論
再起を理解し、またそれを問題に適用するやり方を見つけるのは難しい。 ツリーの問題にあたったとき、次の二つの問を自分に投げかけるといい。 - ノードに対していくつかのパラメーターを与えることで、そのノードから答えを得られるか？ - 子ノードに何のパラメーターを渡すのかについて、定義されたパラメーターもしくは対象ノード自身の値から算出することはできるか？ 両方を満たすなら、トップダウン・アプローチを使うことができる。
もし、対象ノードの子ノードから導かれる答えがわかっていれば、対象ノードの答えがわかるか？これが満たされるなら、ボトムアップ・アプローチを使うことができる。
コードはこちら
