Leetcode Link: 337. 打家劫舍 III - 力扣（LeetCode）
题目
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
解法一
思路：暴力递归
结合题目，很容易的能够写出暴力递归的代码。
本质上我们需要判断对应的节点能否被访问到就行，同时走到每个节点的时候，有两种情况：1) 抢 2) 不抢，我们最终取两者最大即可
题解：
class Solution:
def rob(self, root: TreeNode) -> int:
def process(node):
if not node:
return 0
# 抢这个node
p1 = node.val
if node.left and node.left.left: p1 += process(node.left.left)
if node.left and node.left.right: p1 += process(node.left.right)
if node.right and node.right.left: p1 += process(node.right.left)
if node.right and node.right.right: p1 += process(node.right.right)
# 不抢
p2 = 0
if node.left: p2 += process(node.left)
if node.right: p2 += process(node.right)
return max(p1, p2)
return process(root)解法二
思路：解法一的改进
显然，解法一的问题是没法做记忆化搜索进而改进成动规，我们需要将二叉树变成列表存储的形式才可以，利用下标来访问。
放屁，class node 竟然能做为python字典的key??? 妈了个巴子
题解：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: TreeNode) -> int:
memo = {} # 添加memo
def process(node):
if not node:
return 0
if node in memo.keys():
return memo[node]
# 抢这个node
p1 = node.val
if node.left and node.left.left: p1 += process(node.left.left)
if node.left and node.left.right: p1 += process(node.left.right)
if node.right and node.right.left: p1 += process(node.right.left)
if node.right and node.right.right: p1 += process(node.right.right)
# 不抢
p2 = 0
if node.left: p2 += process(node.left)
if node.right: p2 += process(node.right)
memo[node] = max(p1, p2)
return max(p1, p2)
return process(root)