LeetCode-Solutions/Python/maximum-distinct-path-sum-in-a-binary-tree.py at master · kamyu104/LeetCode-Solutions · 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
# Time:  O(n^2)
# Space: O(n)

# bfs, iterative dfs
class Solution(object):
    def maxSum(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        def bfs():
            adj = [[]]
            vals = [root.val]
            q = [(root, -1)]
            while q:
                new_q = []
                for u, p in q:
                    vals.append(u.val)
                    adj.append([])
                    i = len(adj)-1
                    if p != -1:
                        adj[i].append(p)
                        adj[p].append(i)
                    for node in (u.left, u.right):
                        if not node:
                            continue
                        new_q.append((node, i))
                q = new_q
            return adj, vals

        def iter_dfs(u):
            result = float("-inf")
            total = 0
            lookup = set()
            stk = [(1, u, -1)]
            while stk:
                step, u, p = stk.pop()
                if step == 1:
                    if vals[u] in lookup:
                        continue
                    stk.append((2, u, p))
                    lookup.add(vals[u])
                    total += vals[u]
                    result = max(result, total)
                    for v in adj[u]:
                        if v == p:
                            continue
                        stk.append((1, v, u))
                elif step == 2:
                    total -= vals[u]
                    lookup.remove(vals[u])
            return result

        adj, vals = bfs()
        return max(iter_dfs(u) for u in xrange(len(adj)))


# Time:  O(n^2)
# Space: O(n)
# dfs
class Solution2(object):
    def maxSum(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        def dfs1(u, p):
            vals.append(u.val)
            adj.append([])
            i = len(adj)-1
            if p != -1:
                adj[i].append(p)
                adj[p].append(i)
            for node in (u.left, u.right):
                if not node:
                    continue
                dfs1(node, i)

        def dfs2(u, p):
            if vals[u] in lookup:
                return float("-inf")
            lookup.add(vals[u])
            mx = 0
            for v in adj[u]:
                if v == p:
                    continue
                mx = max(mx, dfs2(v, u))
            lookup.remove(vals[u])
            return vals[u]+mx

        adj, vals = [], []
        dfs1(root, -1)
        lookup = set()
        return max(dfs2(u, -1) for u in xrange(len(adj)))