LintCode 475 [Binary Tree Maximum Path Sum II]

原题

已知一颗二叉树,找到从根节点到任意节点的最大路径和

已知下面一颗二叉树

  1
 / \
2   3

返回4. (1->3)

解题思路

  • Divide and Conquer
  • 借助一个helper函数,从根节点向下分裂,每一层返回左右儿子中的最大值与当前节点的值,层层递归

完整代码

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    """
    @param root the root of binary tree.
    @return an integer
    """
    def maxPathSum2(self, root):
        return self.helper(root)
        
    def helper(self, root):
        if not root:
            return 0
            
        left = self.helper(root.left)
        right = self.helper(root.right)
        
        return max(left, right) + root.val
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容