Algorithm/337.py at master · CC712/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from Utils import pyUtils as utils
root = utils.root


class Solution:
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None or root.val == None:
                return 0
        ans = max(self.recursive(root, root.val, True),
                  self.recursive(root, 0, False))
        print('ans', ans)
        return ans

    def recursive(self, node, ans, lastChoosen):
        # print(ans,lastChoosen)
        if node == None or node.val == None:
            return 0
        # print(node.val)
        getThis = ans
        noGetThis = ans
        v = int(node.val) or 0
        l = node.left
        r = node.right
        if lastChoosen:
            getThis = ans + \
                self.recursive(l, ans, False) + \
                self.recursive(r, ans, False)
        else:
            p1 = self.rob(l)
            p2 = self.rob(r)
            print(p1, p2, ans)
            noGetThis = ans + max(p1, p2)
        a = max(getThis, noGetThis)
        print('mid:',a)
        return a


s = Solution()
s.rob(root)