_1372. Longest ZigZag Path in a Binary Tree.md

1372. Longest ZigZag Path in a Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 05, 2024

Last updated : July 05, 2024

---

Related Topics : Dynamic Programming, Tree, Depth-First Search, Binary Tree

Acceptance Rate : 66.08 %

---

goneLeft() and goneRight() exist to prevent redundant node checks.

Take for instance:

    a           
     \          Checking b-d-e-g (right-left-right-left)
      b         would occur first.
     / \        
    c   d       Once we reach here at (d) however, checking
       / \      d-e-g would be redundant since this direction
      e   f     from this node has already been included in
       \        a the "superset" case, which is guarenteed
        g       to be longer
         \      
          h     

---

Solutions

• m1372.py

Python

m1372.py

# 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:
        goneLeft = set()
        goneRight = set()

        maxx = 0
        toVisit = [root]

        while toVisit :
            curr = toVisit.pop()
            if curr.right and curr not in goneRight :
                cnt = 0
                direction = True
                temp = curr
                while temp :
                    if direction :
                        goneRight.add(temp)
                        temp = temp.right
                    else :
                        goneLeft.add(temp)
                        temp = temp.left
                    direction = not direction
                    cnt += 1
                maxx = max(maxx, cnt - 1)
            
            if curr.left and curr not in goneLeft :
                cnt = 0
                direction = False
                temp = curr
                while temp :
                    if direction :
                        goneRight.add(temp)
                        temp = temp.right
                    else :
                        goneLeft.add(temp)
                        temp = temp.left
                    direction = not direction
                    cnt += 1
                maxx = max(maxx, cnt - 1)

            if curr.right :
                toVisit.append(curr.right)
            if curr.left :
                toVisit.append(curr.left)

        return maxx