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

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


class Solution:
    def maxPathSum(self, root: TreeNode) :
        def put_nodes_into_list(root: TreeNode):
            idx = 0
            nodes = [root]
            while idx != len(nodes):
                node = nodes[idx]
                if node is None or node.left is None and node.right is None:
                    idx += 1
                    continue
                if node.left is not None:
                    node.left.parent = node
                if node.right is not None:
                    node.right.parent = node
                nodes.append(node.left)
                nodes.append(node.right)
                idx += 1
            return nodes
        
        def calculate_max_sum(nodes):
            max_sum = nodes[0].val

            while len(nodes) > 1:
                left = nodes[-2]
                right = nodes[-1]
                parent = left.parent if left is not None else right.parent
                left_val = left.val if left is not None else 0
                right_val = right.val if right is not None else 0
                max_sum = max(max_sum, left_val + parent.val, right_val + parent.val, left_val + parent.val + right_val)
                if left is not None:
                    max_sum = max(max_sum, left_val)
                if right is not None:
                    max_sum = max(max_sum, right_val)
                parent.val = max(parent.val, parent.val + left_val, parent.val + right_val)
                nodes.pop()
                nodes.pop()
            
            return max_sum
        
        nodes = put_nodes_into_list(root)
        return calculate_max_sum(nodes)


n4 = TreeNode(4)
n5 = TreeNode(5)
n2 = TreeNode(2, n4)
n3 = TreeNode(3, None, n5)
n1 = TreeNode(1, n2, n3)

print(Solution().maxPathSum(n1))

n15 = TreeNode(15)
n7 = TreeNode(7)
n20 = TreeNode(20, n15, n7)
n9 = TreeNode(9)
nm10 = TreeNode(-10, n9, n20)

print(Solution().maxPathSum(nm10))

n2 = TreeNode(2)
n3 = TreeNode(3)
n1 = TreeNode(1, n2, n3)

print(Solution().maxPathSum(n1))

# %%

nodes = [1, 2, 3, 4]
print(nodes)
nodes.pop()
nodes.pop()
print(nodes)
# %%

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

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


class Solution:
    def maxPathSum(self, root: TreeNode) :
        def put_nodes_into_list(root: TreeNode):
            idx = 0
            nodes = [root]
            while idx != len(nodes):
                node = nodes[idx]
                if node is None or node.left is None and node.right is None:
                    idx += 1
                    continue
                if node.left is not None:
                    node.left.parent = node
                if node.right is not None:
                    node.right.parent = node
                nodes.append(node.left)
                nodes.append(node.right)
                idx += 1
            return nodes
        
        def calculate_max_sum(nodes):
            max_sum = nodes[0].val

            while len(nodes) > 1:
                left = nodes[-2]
                right = nodes[-1]
                parent = left.parent if left is not None else right.parent
                left_val = left.val if left is not None else 0
                right_val = right.val if right is not None else 0
                max_sum = max(max_sum, left_val + parent.val, right_val + parent.val, left_val + parent.val + right_val)
                if left is not None:
                    max_sum = max(max_sum, left_val)
                if right is not None:
                    max_sum = max(max_sum, right_val)
                parent.val = max(parent.val, parent.val + left_val, parent.val + right_val)
                nodes.pop()
                nodes.pop()
            
            return max_sum
        
        nodes = put_nodes_into_list(root)
        return calculate_max_sum(nodes)


n4 = TreeNode(4)
n5 = TreeNode(5)
n2 = TreeNode(2, n4)
n3 = TreeNode(3, None, n5)
n1 = TreeNode(1, n2, n3)

print(Solution().maxPathSum(n1))

n15 = TreeNode(15)
n7 = TreeNode(7)
n20 = TreeNode(20, n15, n7)
n9 = TreeNode(9)
nm10 = TreeNode(-10, n9, n20)

print(Solution().maxPathSum(nm10))

n2 = TreeNode(2)
n3 = TreeNode(3)
n1 = TreeNode(1, n2, n3)

print(Solution().maxPathSum(n1))

# %%

nodes = [1, 2, 3, 4]
print(nodes)
nodes.pop()
nodes.pop()
print(nodes)
# %%

# https://leetcode.com/problems/binary-tree-maximum-path-sum/ #%% # Definition for a binary tree node. # %% # %%