BinarySearch 0089 Longest Tree Sum Path From Root to Leaf

Problem statement

https://binarysearch.com/problems/Longest-Tree-Sum-Path-From-Root-to-Leaf/

Solution

The idea is to use dfs(node, val, dep), where node is current node we are in, val is sum of values from node to root and dep is the depth of node.

Complexity

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

Code

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

        self.ans = (0, 0)
        dfs(root, 0, 0)
        return self.ans[1]