[数据结构与算法]力扣337.打家劫舍III

题目来源： 337.打家劫舍III
题目： 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。


思路：动态规划 通过后续遍历的方法，每次寻找到当前结点的最优值，接着依次遍历二叉树，得到最终 的最优值，即小偷偷取的最高金额。
中间需要注意的一点是，创立两个空间用于存储该结点打劫或不打劫。如果打劫的话当前结点的最优值等于左子树不打劫的最优值+右子树不打劫的最优值+当前结点的值；如果不打劫的话，当前结点的最优值等于左子树打劫或不打劫的最大值+右子树打劫或不打劫的最大值（因为当前结点不打劫的时候不知道左右子树大不打劫，所以只能取打劫或不打劫两种情况的最大值）
python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dps(root):
            if not root:
                return [0, 0]
            ans = [0, 0]
            # 左子树打劫以后的情况
            left = dps(root.left)
            #右子树打劫以后的情况
            right = dps(root.right)
            ans[0] = max(left[0], left[1]) + max(right[0], right[1])
            ans[1] = left[0] + right[0] + root.val
            return ans
        ans = dps(root)
        return max(ans[0], ans[1])

参考链接：LeetCode 337. 打家劫舍 III | Python
【Leetcode】Python版每日一题（20200805）：337. 打家劫舍 III(树上动态规划)
力扣题目337-打家劫舍III