BinarySearch 0189 Delete Even Leaves

Problem statement

https://binarysearch.com/problems/Delete-Even-Leaves/

Solution

Use recursion here: preorder traversal. First, solve subproblems for the left and the right subtrees and then decide what to return root or None.

Complexity

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

Code

class Solution:
    def solve(self, root):
        if not root: return
        root.left = self.solve(root.left)
        root.right = self.solve(root.right)
        if root.val % 2 or root.left or root.right:
            return root
        else:
            return None