怎么抓小偷

有一个小区的别墅以二叉树结构坐落。除了第一栋别墅，别的别墅都与另一栋”源头”别墅连接。一旦小偷闯入相邻的两栋别墅，警铃就会被触发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def rob(self, root):
    a = self.helper(root)       # a 为一个二维数组，表示root的[偷值, 不偷值]
    return max(a[0], a[1])


def helper(self, root):
    if root is None:
        return [0, 0]
    left = self.helper(root.left)
    right = self.helper(root.right)
    rob_value = root.val + left[1] + right[1]                        # root的偷值
    skip_value = max(left[0], left[1]) + max(right[0], right[1])     # root的不偷值
    return [rob_value, skip_value]

二叉树中的最大路径和

二叉树的节点可正可负，要保证路线总和的最大。 

1
2