[Leetcode] 1372. Longest ZigZag Path in a Binary Tree

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

initial

I was so close to getting the actual solution.
So this zigzag path doesnt necessarily start from the root node.
So I tried traversing from every node.

class Solution:
    def __init__(self):
        self.ans=0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        def dfs(root,count,flag):
            if root is None:
                return
            self.ans = max(self.ans, count)
            if flag:
                dfs(root.right,count+1,False)
                dfs(root.left,1,True)
            else:
                dfs(root.left,count+1,True)
                dfs(root.right,1,False)

        def traverse(hola):
            # true = left, false= right
            dfs(root,0,True)
            dfs(root,0,False)
            traverse(root.left)
            traverse(root.right)
        traverse(root)
        return self.ans

But notice this traverse method.
Firstly there is no return condition so it goes on infinite loop. Second, there is a lot of repetitive work. Thirdly it should be hola, not root.

If u really wanna fix, (still geting runtime error)

        def traverse(hola):
            if not hola:
                return
            # true = left, false= right
            dfs(hola,0,True)
            dfs(hola,0,False)
            traverse(hola.left)
            traverse(hola.right)

solution

Instead of dfs on every node, we can actually do 2 dfs - one is to continue the correct path. But if there is an invalid path like (right->left-> theres left child node available for traversal), then we can set a new path then as length = 0

class Solution:
    def __init__(self):
        self.ans=0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        def dfs(root,count,flag):
            if root is None:
                return
            self.ans = max(self.ans, count)
            if flag:
                dfs(root.right,count+1,False)
                dfs(root.left,1,True)
            else:
                dfs(root.left,count+1,True)
                dfs(root.right,1,False)

        def traverse(hola):
            # true = left, false= right
            dfs(root,0,True)
            dfs(root,0,False)

        traverse(root)
        return self.ans

Even this can be optimised

much better (i dont get)

class Solution:
    def __init__(self):
        self.ans=0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        # DFS function to track the ZigZag path
        def dfs(node, left_length, right_length):
            if node is None:
                return
            # Update the global answer to store the maximum ZigZag length
            self.ans = max(self.ans, left_length, right_length)

            # Move left, update right_length, reset left_length
            dfs(node.left, right_length + 1, 0)
            # Move right, update left_length, reset right_length
            dfs(node.right, 0, left_length + 1)

        # Start DFS traversal
        dfs(root, 0, 0)
        
        return self.ans

So i think for example when moving left, we get the previous right length and increment it cuz it is correct path. But i dont really gett this resetting part.

revisited may 26th 25

So notice we are incrementing left length with right length +1 to continue valid path if there is a valid path.

From root node 1:
Go left to 2 → direction: LEFT → left_length = 1, right_length = 0

From 2, go right to 4 → direction: LEFT → RIGHT → left_length = 0, right_length = 2

From 4, go left to 6 → direction: LEFT → RIGHT → LEFT → left_length = 3, right_length = 0

how do u even think of this logic lol

complexity

o(n) time and o(h) space