Sponsored
Sponsored
The 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.
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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def longestZigZag(self, root: TreeNode) -> int:
9 def dfs(node, direction, length):
10 nonlocal max_len
11 if not node:
12 return
13 max_len = max(max_len, length)
14 if direction == 0: # left
15 dfs(node.left, 1, length + 1)
16 dfs(node.right, 0, 1)
17 else: # right
18 dfs(node.left, 1, 1)
19 dfs(node.right, 0, length + 1)
20
21 max_len = 0
22 dfs(root, 0, 0) # Start direction as left
23 dfs(root, 1, 0) # Start direction as right
24 return max_lenThis 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.
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.
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.
1#include <iostream>
2#include <queue>
3
4using namespace std;
5
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int longestZigZag(TreeNode* root) {
int maxLen = 0;
queue<pair<TreeNode*, pair<int, int>>> q; // (node, (direction, length))
q.push({root, {0, 0}}); // Start with left
q.push({root, {1, 0}}); // Start with right
while (!q.empty()) {
auto [node, state] = q.front(); q.pop();
int direction = state.first, length = state.second;
maxLen = max(maxLen, length);
if (node->left)
q.push({node->left, {1, direction == 0 ? length + 1 : 1}});
if (node->right)
q.push({node->right, {0, direction == 1 ? length + 1 : 1}});
}
return maxLen;
}
};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.