Binary Tree Maximum Path Sum

質問する

pathは最大1回しかノードを通らないedgeの連続

通根不要

path sum銀通路のノード値の和

max path sum

non-empty path

に答える

ルートから再帰

上向きに計算した左+根、右+根、左+rigt+根、根が現在のサブツリーの最大path sum

左+右+根は今が最後なので残りはmaxを返して大きくする

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        global path
        path = set()
        recursion(root)
        return max(path)
        
        
def recursion(root):
    global path
    leftTree, rightTree = 0, 0
    
    if root.left:
        leftTree = recursion(root.left)
    if root.right:
        rightTree = recursion(root.right)
    
    pathSum = [root.val]
    pathSum.append(leftTree + root.val) # left+root
    pathSum.append(rightTree + root.val) # right+root
    pathSum.append(leftTree + rightTree + root.val) # left + right + root
    
    path.add(max(pathSum))
    return max(pathSum[:3])

結果

回転するたびに速度が違う...速度は76.87%に達する可能性があります
別の解釈

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        global maxi
        maxi = -1001
        recursion(root)
        return maxi
        
        
def recursion(root):
    global maxi
    leftTree, rightTree = 0, 0
    
    if root.left:
        leftTree = recursion(root.left)
    if root.right:
        rightTree = recursion(root.right)
    
    pathSum = [root.val]
    pathSum.append(leftTree + root.val) # left+root
    pathSum.append(rightTree + root.val) # right+root
    pathSum.append(leftTree + rightTree + root.val) # left + right + root
    
    maxi = max(maxi, max(pathSum))
    return max(pathSum[:3])    

これはsetではなくmax演算を返した

大差ない