BinarySearch 1021 Subtree with Maximum Value

Problem statement

https://binarysearch.com/problems/Subtree-with-Maximum-Value/

Solution

Just do what is asked, using dfs/bfs. Similar to Leetcode 1120 Maximum Average Subtree.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        self.ans = 0

        def dfs(node):
            if not node: return 0
            ans = dfs(node.left) + dfs(node.right) + node.val
            self.ans = max(self.ans, ans)
            return ans
        
        dfs(root)
        return self.ans