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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int LongestZigZag(TreeNode root) {
int maxLength = 0;
var queue = new Queue<(TreeNode Node, int Direction, int Length)>();
queue.Enqueue((root, 0, 0));
queue.Enqueue((root, 1, 0));
while (queue.Count > 0) {
var (node, direction, length) = queue.Dequeue();
maxLength = Math.Max(maxLength, length);
if (node.left != null) {
queue.Enqueue((node.left, 1, direction == 0 ? length + 1 : 1));
}
if (node.right != null) {
queue.Enqueue((node.right, 0, direction == 1 ? length + 1 : 1));
}
}
return maxLength;
}
}The C# implementation of the BFS approach follows a similar pattern to the C++ solution. A queue is used to efficiently traverse each level of the tree, switching directions and updating path lengths. The tuple structure is maintained in each queue entry to keep state information, and maxLength is adjusted to capture the longest path identified.