BinarySearch 0217 Maximum Non-Adjacent Tree Sum

Problem statement

https://binarysearch.com/problems/Maximum-Non-Adjacent-Tree-Sum/

Solution

Equal to Leetcode 0337. House Robber III.

Complexity

Time is O(n), space is O(h).

Code

class Solution:
    def solve(self, root):
        def dfs(node):
            if not node: return [0, 0]
            L = dfs(node.left)
            R = dfs(node.right)
            return [node.val + L[1] + R[1], max(L) + max(R)]
        
        return max(dfs(root))