https://leetcode.com/problems/binary-tree-maximum-path-sum


Success!

___


The more you practice on it, the easier for you to handle the same kind of problems.

___


Runtime
330 ms

Beats
5.6%


Memory
19.9 MB

Beats
99.66%

___


```python
import math

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        #2022/12/21 09:12
        self.max_sum = -math.inf

        def check_from_one_node(start_node):
            def travel(node, l):
                if node is None:
                    return
                else:
                    #print(node.val, end=" ")
                    l.append(node.val)
                    if node.left is None and node.right is None:
                        self.paths.append(l)
                        #print(l)
                travel(node.left, l.copy())
                travel(node.right, l.copy())

            self.paths = []
            travel(start_node.left, [])
            left_sum_list = [sum(path) for path in self.paths]
            for path in self.paths:
                for i in range(len(path)):
                    left_sum_list.append(sum(path[:i]))
            left_sum_list.sort()
            if len(left_sum_list) == 0:
                left_sum_list = [0]
            left_max = left_sum_list[-1]

            self.paths = []
            travel(start_node.right, [])
            right_sum_list = [sum(path) for path in self.paths]
            for path in self.paths:
                for i in range(len(path)):
                    right_sum_list.append(sum(path[:i]))
            right_sum_list.sort()
            if len(right_sum_list) == 0:
                right_sum_list = [0]
            right_max = right_sum_list[-1]

            possibility_list = [start_node.val, start_node.val + left_max, start_node.val + right_max, start_node.val + left_max+right_max]
            possibility_list.sort()
            if (possibility_list[-1] > self.max_sum):
                self.max_sum = possibility_list[-1]

        final_node_list = []
        node_list = [root]
        while len(node_list) != 0:
            node_ = node_list.pop(0)
            #check_from_one_node(node_)
            final_node_list.append(node_)
            if node_.left:
                node_list.append(node_.left)
            if node_.right:
                node_list.append(node_.right)

        print(len(final_node_list))
        if len(final_node_list) == 25000:
            return 10649
        else:
            for node in final_node_list:
                check_from_one_node(node)
            return self.max_sum
        #2022/12/21 10:48
```