Python solution.Dynamic programming, DFS, Recursive


  • 0
    L
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def maxPathSum(self, root):
            ''' 动态规划。如果题目中限制条件是都是大于等于零的数,则充其量为Medium,
                考虑负数之后会有很多需要处理的边界情况,难度增加了不少。
            '''
            def PathSum(root):
                """
                :rtype: int [left, right, max]
                left:表示以左子树某个节点为起点时,到左子树根节点的最大值
                right:表示以右子树某个节点为起点时,到右子树根节点的最大值
                max:表示左子树中,所有路径中的最大和
                """
                if root == None:    # 当前节点为空,返回[0,0,0],计算最大值时,空节点不能使用
                    return [0]*3
                if root.left==None and root.right==None:    # 当前节点左右子树为空,则当前节点为叶子节点,[left, right, max]设置为当前节点值
                    return [root.val]*3
                    
                left = PathSum(root.left)    # 递归调用,得到左子树状态信息
                right = PathSum(root.right)    # 递归调用,得到右子树状态信息
                
                """ 状态信息计算,前两个left,right容易计算,max比较难计算 """
                r_root = [0]*3
                # left
                left_max = max(left[0],left[1])+root.val    # 计算[left, ~, ~]。(只计算left)
                r_root[0] = (left_max >= root.val) and left_max or root.val    # 起点从左子树某个几点开始,或者是从当前节点开始。
                # left
                right_max = max(right[0],right[1])+root.val    # 计算[~, right, ~]
                r_root[1] = (right_max >= root.val) and right_max or root.val
                
                ## 最大值,对最大值的处理要格外小心
                if root.left == None and root.right != None:    # 当前节点没有左子树,所以在计算[~, ~, max]时,不考虑左子树状态
                    left_max_list = [max(right[0],right[1]), root.val, max(right[0],right[1])+root.val]
                    r_max = max(left_max_list)
                    r_root[2] = r_max >= right[2] and r_max or right[2]
                if root.left != None and root.right == None:    # 当前节点没有右子树,不考虑右子树状态
                    right_max_list = [max(left[0],left[1]), root.val, max(left[0],left[1])+root.val]
                    r_max = max(right_max_list)
                    r_root[2] = r_max >= left[2] and r_max or left[2]
                
                if root.left != None and root.right != None:    # 当前节点拥有左子树和右子树,状态信息都要考虑
                    max_list = [max(left[0],left[1]),root.val,max(right[0],right[1])]
                    max_list.append(max_list[0]+max_list[1])
                    max_list.append(max_list[1]+max_list[2])
                    max_list.append(max_list[0]+max_list[1]+max_list[2])
                    r_max = max(max_list)
                    if left[2]>=right[2] and root.left!=None:    # 拥有最大sum的路径,不一定经过当前节点
                        r_root[2] = r_max >= left[2] and r_max or left[2]
                    elif left[2]<=right[2] and root.right!=None:
                        r_root[2] = r_max >= right[2] and r_max or right[2]
                """ 处理好这一部分是关键 """
                
                return r_root
            result = PathSum(root)
            return result[2]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.