BinarySearch 0082 Largest Root to Leaf Sum

Problem statement

https://binarysearch.com/problems/Largest-Root-to-Leaf-Sum/

Solution

Traverse tree with dfs(node, val), where node is current node we reached and val is current sum from root to this node.

Complexity

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

Code

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

        self.ans = 0
        dfs(root, 0)
        return self.ans