【LeetCode with Python】 124. Binary Tree Maximum Path Sum

题目

原题页面：https://leetcode.com/problems/binary-tree-maximum-path-sum/
本文地址：http://leetcode.xnerv.wang/binary-tree-maximum-path-sum/
题目类型：Tree, Depth-first Search
难度评价：Hard
类似题目：(M) Path Sum, (M) Sum Root to Leaf Numbers

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

1
/ \
2 3

Return 6.

分析

本是比较简单的一道二叉树递归算法题目，也花了一些时间。主要还是在题意的理解中，本题要求的“最大路径和”，不一定经过了root，起点和终点可以是同一个点（即整个路径只有一个点）。
注意用一个类成员变量max来记录搜索过程中出现过的最大路径和，最后需要返回的就是这个max值。
此外还有一点容易搞错，当一棵子树计算完退栈时，向上一层返回的应该是该子树左路径、右路径中的最大值，而不是该子树中的“最大路径和”，因为从父节点搜索进入该子树时，只能选择其左分支或者右分治进入。
最后需要注意的一点是，这道题目并没有说节点的值是正数或者自然数，考虑到leetcode一贯的尿性，最好认为负数也是会出现的。

代码

class Solution:
    def __init__(self):
        self.max = None

    def doMaxPathSum(self, root):
        if None == root:
            return 0
        left_sum = self.doMaxPathSum(root.left)
        right_sum = self.doMaxPathSum(root.right)
        max_left_sum = max(left_sum, 0)
        max_right_sum = max(right_sum, 0)
        cur_max = max_left_sum + max_right_sum + root.val
        if None == self.max or cur_max > self.max:
            self.max = cur_max
        return max(max_left_sum + root.val, max_right_sum + root.val)

    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        self.doMaxPathSum(root)
        return self.max