AI大模型项目课 数据科学集训营 编程算法 系统设计 SQL 成功案例 免费资源 1对1 问答论坛
加入免费会员

编程算法面试常考题答案汇总

Maximum Path Sum from Leaf to Leaf

 

 

Coding Interview Question: Maximum Path Sum from Leaf to Leaf

 

Given the root of a binary tree, return the maximum sum of a path between any two leaves in the binary tree. You may assume that the binary tree is not skewed and contains at-least two nodes.

Solution

  
#  本代码来自 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

 

如果大家对题目代码有任何问题，欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信。期待与同学们继续交流！