Matsushita's Blog

House robber ⅲ in LeetCode

問題

2分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。

条件

  • 直接つながれている隣同士のノードは取る事ができない。

House Robber III - LeetCode

解き方

それぞれのノードについて、そのノードの値を和に含めるか否かの2パターンを試し、最大値となる和を取得する。その際、同じ条件での探索が複数存在するのでメモ化することで計算量を抑えることができる。

ソースコード

My Simple and Clear Java Solution With Using Memoization | LeetCode Discuss