You are given the root of a binary tree.
A ZigZag path for a binary tree is defined as follow:
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
Return the longest ZigZag path contained in that tree.
Example 1:
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1] Output: 3 Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:
Input: root = [1,1,1,null,1,null,null,1,1,null,1] Output: 4 Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:
Input: root = [1] Output: 0
Constraints:
[1, 5 * 104].1 <= Node.val <= 100The recursive DFS approach involves traversing the binary tree starting from each node, keeping track of the length of the path and the direction of the last move. We use recursion to explore all possible ZigZag paths, switching directions (left to right or right to left) at each step and updating the maximum path length observed.
This Python solution defines a recursive function dfs that explores each node of the tree. For each node, it checks both directions and tracks the length of the ZigZag path in each possible direction. A global variable max_len is updated whenever a longer path is found. The initial calls to dfs start with both left and right as the initial directions.
JavaScript
Time Complexity: O(N) where N is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(H) where H is the height of the tree, due to the recursion stack.
The BFS iterative approach involves using a queue to traverse the tree level by level while keeping track of the direction and length of each ZigZag path. At each node, the direction is switched, and we continue exploring all potential ZigZag paths, updating the maximum found path length.
This C++ solution uses a queue to perform a breadth-first search (BFS) on the binary tree. Each queue entry contains a node along with a pair indicating the direction and current length of the ZigZag path. As we explore the tree, we push new nodes into the queue with the opposite direction and updated lengths. maxLen is continually updated with the longest path found.
C#
Time Complexity: O(N) due to a single traversal of all nodes.
Space Complexity: O(N) for storing nodes and their states in the queue.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Recursive Approach | Time Complexity: O(N) where N is the number of nodes in the tree, as each node is visited once. |
| Breadth-First Search (BFS) Iterative Approach | Time Complexity: O(N) due to a single traversal of all nodes. |
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python • NeetCodeIO • 23,003 views views
Watch 9 more video solutions →Practice Longest ZigZag Path in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor