Longest ZigZag Path in a Binary Tree - LeetCode 1372 - Python Solution
Solution Blog: (sign into leetcode to view):
https://leetcode.com/problems/longest...
Base Case:
When you hit a leaf node, return the depth and it'll propagate up the tree and be returned!
Two Paths from here:
If you went left previously, take the maximum of:
1. the current depth
2. now going down the right path, and incrementing the depth by 1
3. go down the left path AGAIN, and reset depth to 0
Then repeat this logic (but reversed) for if you went right previously.
Time complexity: O(N)
Space complexity: O(N)