通りや家々を略奪した後、泥棒は新しいエリアを見つけます。このエリアには「ルート」と呼ばれる入り口が1つだけあります。 ルート」とは別に、各家には「親」家が1軒だけつながっています。いくつかの偵察の後、賢い泥棒は「この場所のすべての家の配置が二股に分かれた木に似ている」ことに気づきます。 もし、同じ夜に直接つながっている2つの家に泥棒が入った場合、その家は自動的に警察に通報します。
アラームを作動させずに、泥棒が一晩で盗める最高額を計算します。
例題
- 例1
: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
: 7
: 泥棒が一晩で盗める最高額 = 3 + 3 + 1 = 7.
- 例2
: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
: 9
: 泥棒が一晩で盗める最高額 = 4 + 5 = 9.
推論
- 既知の接続ノードが累積することはできませんし、任意の1つのノードを選択すると、このノードが含まれていないこのノードを含む2つのグループに分けることができます。
- このノードを含む結果をdpRootで保存します。
- dpは、このノードを含まない結果を保存します。
ノードを設定します：
- ノードを含む,dpRoot[node]はこのノードの値＋含まれない隣接ノードの値に等しい dpRoot[node] = node.val+dp[node.left]+dp[node.right］
- dpRootLeft[node.left] [node.left]
特殊条件と再帰的終了条件
- ルート擬似ヌルは0を返します
- 最後のノード null まで再帰し、再帰を終了します。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function (root) {
if (root === null) return 0
// バイナリツリーでノードの値が重複する可能性がある場合、マップを使ってノードの位置を記録する
let dpRoot = new Map(), // キーを含むノード
dp = new Map() // キーを含まないノード
function dfs(node) {
// 再帰的終了
if (node === null) return 0
// 再帰的列挙はノードを含む.left
dfs(node.left)
// 再帰的列挙はノードを含む.right
dfs(node.right)
let dpRootLeft = dpRoot.get(node.left) || 0,
dpRootRight = dpRoot.get(node.right) || 0,
dpLeft = dp.get(node.left) || 0,
dpRight = dp.get(node.right) || 0
// この入力ノードを含む
dpRoot.set(node, node.val + dpLeft + dpRight)
// 入力ノードを含めないことを選択する
dp.set(node, Math.max(dpRootLeft, dpLeft) + Math.max(dpRootRight, dpRight))
}
// に基づいて，点を含むケースを再帰的に列挙する．
dfs(root)
return Math.max(dpRoot.get(root), dp.get(root))
}
- dpRootもdpも、計算にはその隣接ノードの値に依存するので
- そして、包含と除外の2つの可能性を再帰的に返すことができます。
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function (root) {
let [dpRoot, dp] = dfs(root)
function dfs(root) {
if (root === null) return [0, 0]
// 左ノードと右ノードをそれぞれ含む場合の列挙
let [dpRootLeft, dpLeft] = dfs(root.left),
[dpRootRight, dpRight] = dfs(root.right)
let dpRoot = root.val + dpLeft + dpRight,
dp = Math.max(dpRootLeft, dpLeft) + Math.max(dpRootRight, dpRight)
return [dpRoot, dp]
}
return Math.max(dpRoot, dp)
}
- つまり、node.valはnode.leftおよびnode.rightと同じグループにはありません。
- robを再帰的に呼び出すと、入力点を含まない、入力ノードを含む和の最大値が返されます。
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function (root) {
// 再帰的終了条件
if (root == null) return 0
let Root = 0,// ルートノードを含む
noRoot = 0 // ルート・ノードを含まない
// 存在する非隣接ノードを累積する
let Root = root.val
if (root.left) {
Root += rob(root.left.left) + rob(root.left.right)
}
if (root.right) {
Root += rob(root.right.left) + rob(root.right.right)
}
// ルートノードなしのノード累積
let noRoot = rob(root.left) + rob(root.right)
return Math.max(Root, noRoot)
}
ブログ：
出版：The Pit's Little Bookie
