BinarySearch 0877 Vertical Lines in Binary Tree

Problem statement

https://binarysearch.com/problems/Vertical-Lines-in-Binary-Tree/

Solution

Use dfs to traverse our tree, use -1 when we go the the left and +1 when we go to the right.

Complexity

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

Code

class Solution:
    def solve(self, root):
        def dfs(node, d):
            if not node: return 
            self.mn = min(self.mn, d)
            self.mx = max(self.mx, d)
            dfs(node.left, d - 1)
            dfs(node.right, d + 1)

        self.mn, self.mx = 0, 0
        dfs(root, 0)
        return self.mx - self.mn + 1