CodingInterviewQuestions/Leetcode/Leetcode Problem 124 Binary Tree Maximum Path Sum.txt at master · akuchotrani/CodingInterviewQuestions · 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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
124. Binary Tree Maximum Path Sum
Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Hint to solve: Use recrusive calls to left and right. Keep track of max.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def calculatePathSumRecursive(self, root)->int:
        if root is None:
            return 0

        left = max(0, self.calculatePathSumRecursive(root.left))
        right = max(0, self.calculatePathSumRecursive(root.right))

        currentMax = left + right + root.val
        self.maxSum = max(self.maxSum, currentMax)

        return max(left,right) + root.val


    def maxPathSum(self, root: TreeNode) -> int:
        self.maxSum = -sys.maxsize

        self.calculatePathSumRecursive(root)

        return self.maxSum


Alternate Solution


Binary Tree Maximum Path Sum


A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.


Example 1:


Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:


Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.


Constraints:

The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000


Traverse the tree and calculate left sum, right sum, all three node sum
while returning to the caller only return left sum, right sum, current val (Total sum is not included as it could be disjoint)


def maxPathSum(self, root: Optional[TreeNode]) -> int:

    def recurse(node):
        global answer

        if(node == None):
            return 0

        leftSum = recurse(node.left)
        rightSum = recurse(node.right)
        total_all = node.val + leftSum + rightSum
        total_left = node.val + leftSum
        total_right = node.val + rightSum
        total = max(node.val, total_all, total_left, total_right)
        if(total > answer):
            answer = total
        return max(node.val, total_left, total_right)

    global answer
    answer = -math.inf
    recurse(root)
    return answer