Problem statement

https://binarysearch.com/problems/ZigZag-Path/

Solution

Just use dfs, where answer is the longest zigzag path starting with left move and with right move.

Complexity

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

Code

class Solution:
    def solve(self, root):
        self.ans = 0
        def dfs(node):
            if not node: return (0, 0)
            l1, l2 = dfs(node.left)
            r1, r2 = dfs(node.right)
            ans = (r2 + 1, l1 + 1)
            self.ans = max(self.ans, r2 + 1, l1 + 1)
            return ans
        
        dfs(root)
        return self.ans