628. Maximum Subtree

LintCode 炼码 - ChatGPT！更高效的学习体验！

subtree问题，维护一个全局变量，遍历整个tree

class Solution:
    """
    @param root: the root of binary tree
    @return: the maximum weight node
    """
    def __init__(self):
        self.maxSum = float("-inf")
        self.res = TreeNode(0)
        
    def findSubtree(self, root):
        # write your code here
        self.traversal(root)
        return self.res if root else root
    
    def traversal(self, root):
        if not root: return 0
        left = self.traversal(root.left)
        right = self.traversal(root.right)
        curSum = left+right+root.val
        if curSum > self.maxSum:
            self.maxSum = curSum
            self.res = root
        return curSum