#  本代码来自 Techie科技求职，由 Techie Learning,Inc 原创
#  - Techielearning.com 是来自硅谷的科技职业发展平台。
#  - 本代码所属课程：<< Techie编程算法集训营 >>
#  - 12周56+课时精品内容，精讲软件工程师编程算法面试核心知识体系。
#  - 120道面试真题详解，27类常考题型剖析，1对1面试辅导与专业答疑。
#  - 官方网站：https://www.techielearning.com/
#  - 版权所有，禁止转发和分享

#  - Input:
#
#               1
#             /   \
#            /     \
#           2       3
#            \     / \
#            -4   5   6
#            / \
#           7   8
#
#  - Output: 22
#  - Explanation: The maximum sum path between two leaves is [8, 5, 3, 6].

    from collections import namedtuple

    class Solution:
      def findMaximumSum(self, root: Node) -> int:
        Result = namedtuple('Result', ['leaf_to_leaf', 'root_to_leaf'])
        def s(root):
          if not root.left and not root.right:
            return Result(float('-inf'), root.data)
          if root.left and root.right:
            l, r = s(root.left), s(root.right)
            return Result(
              leaf_to_leaf = max(
                l.leaf_to_leaf,
                r.leaf_to_leaf,
                l.leaf_to_leaf + r.root_to_leaf + root.data
              ),
              root_to_leaf = max(l.root_to_leaf, r.root_to_leaf) + root.data
            )
          if root.left:
            l = s(root.left)
            return Result(l.leaf_to_leaf, l.root_to_leaf + root.data)
          else:
            r = s(root.right)
            return Result(r.leaf_to_leaf, r.root_to_leaf + root.data)
        return s(root).leaf_to_leaf