Leetcode Problem 1372. Longest ZigZag Path in a Binary Tree

1372. Longest ZigZag Path in a Binary Tree

Leetcode Solutions

Depth First Search (DFS) for Longest ZigZag Path

  1. Initialize a global variable max_length to store the maximum ZigZag path length found so far.
  2. Define a recursive function dfs(node, direction, length) where node is the current tree node, direction is a boolean indicating whether to go left (true) or right (false), and length is the current ZigZag path length.
  3. If the current node is null, return from the function.
  4. Update max_length with the maximum of its current value and length.
  5. If direction is true, recursively call dfs(node.left, false, length + 1) to continue the ZigZag path to the left, and dfs(node.right, true, 1) to start a new path to the right.
  6. If direction is false, recursively call dfs(node.right, true, length + 1) to continue the ZigZag path to the right, and dfs(node.left, false, 1) to start a new path to the left.
  7. Start the DFS traversal by calling dfs(root, true, 0) and dfs(root, false, 0).
  8. Return the value of max_length as the result.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...