Problem statement

https://binarysearch.com/problems/Elephant-Tree/

Solution

Just use postorder dfs here: first solve for the left and the right subtrees, than update node.

Complexity

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

Code

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

        dfs(root)
        return root