Devin's Blog

Longest ZigZag Path in a Binary Tree

2 min read

Summary

I did not reset the depth.

The Tree that Messed Me up

[1,1,null,null, 1, null, 1, 1, null, null, 1]

My Answer Altered by ChatGPT

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        self.longest_path = 0
 
        def zigStartingFromLeft(node, depth=0):
            if not node:
                return
 
            self.longest_path = max(self.longest_path, depth)
            zigStartingFromRight(node.right, depth + 1)
            zigStartingFromLeft(node.left, 1)
 
        def zigStartingFromRight(node, depth=0):
            if not node:
                return
 
            self.longest_path = max(self.longest_path, depth)
            zigStartingFromLeft(node.left, depth + 1)
            zigStartingFromRight(node.right, 1)
 
        zigStartingFromLeft(root.left, 1)
        zigStartingFromRight(root.right, 1)
 
        return self.longest_path

My Answer before Amended to Include a Global Variable

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        maxPathLength = 0
        def zigStartingFromLeft(node):
            nonlocal maxPathLength
 
            if not node:
                return 0
 
            rightZigSum = 1 + zigStartingFromRight(node.right)
            leftZigSum = zigStartingFromLeft(node.left)
            maxLocalPathLength = max(rightZigSum, leftZigSum)
            maxPathLength = max(maxPathLength, maxLocalPathLength)
        
            return maxLocalPathLength
 
        def zigStartingFromRight(node):
            nonlocal maxPathLength
 
            if not node:
                return 0
 
            rightZigSum = zigStartingFromRight(node.right)
            leftZigSum = 1 + zigStartingFromLeft(node.left)
            maxLocalPathLength = max(rightZigSum, leftZigSum)
            maxPathLength = max(maxPathLength, maxLocalPathLength)
        
            return maxLocalPathLength
 
        zigStartingFromLeft(root.left)
        zigStartingFromRight(root.right)
        
        return maxPathLength

My Original Answer without Keeping Track of Global counter

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        def zigStartingFromLeft(node):
            if not node:
                return 0
            
            return max(1 + zigStartingFromRight(node.right), zigStartingFromLeft(node.left))
 
        def zigStartingFromRight(node):
            if not node:
                return 0
            
            return max(zigStartingFromRight(node.right), 1 + zigStartingFromLeft(node.left))
 
        return max(zigStartingFromLeft(root.left), zigStartingFromRight(root.right))

References

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/

Graph View