Dare2Solve
The problem involves finding the longest zigzag path in a binary tree. A zigzag path is defined as a sequence of nodes where the direction of movement alternates between left and right at each step. The task is to return the length of the longest such path.
The zigzag path can be determined by traversing the tree in a depth-first manner. At each node, we decide whether to continue the zigzag by moving in the opposite direction or to reset the count if we move in the same direction. The key idea is to maximize the length of the path by alternating between left and right directions.
Depth-First Search (DFS):
Termination:
O(N)
, where N
is the number of nodes in the tree. Each node is visited once during the DFS traversal.
O(H)
, where H
is the height of the tree. This space is used by the recursive stack during the DFS.
class Solution {
public:
int maxZigZag = 0;
void dfs(TreeNode* node, char last, int length) {
if (!node) return;
maxZigZag = std::max(maxZigZag, length);
dfs(node->left, 'l', last != 'l' ? length + 1 : 1);
dfs(node->right, 'r', last != 'r' ? length + 1 : 1);
}
int longestZigZag(TreeNode* root) {
dfs(root, 'l', 0);
return maxZigZag;
}
};
# 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 __init__(self):
self.max_zigzag = 0
def dfs(self, node, last, length):
if not node:
return
self.max_zigzag = max(self.max_zigzag, length)
self.dfs(node.left, 'l', length + 1 if last != 'l' else 1)
self.dfs(node.right, 'r', length + 1 if last != 'r' else 1)
def longestZigZag(self, root: TreeNode) -> int:
self.dfs(root, 'l', 0)
return self.max_zigzag
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int maxZigZag = 0;
private void dfs(TreeNode node, char last, int length) {
if (node == null) return;
maxZigZag = Math.max(maxZigZag, length);
dfs(node.left, 'l', last != 'l' ? length + 1 : 1);
dfs(node.right, 'r', last != 'r' ? length + 1 : 1);
}
public int longestZigZag(TreeNode root) {
dfs(root, 'l', 0);
return maxZigZag;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var longestZigZag = function (root) {
let max = 0;
let dfs = (node, last, length) => {
if (!node) return;
max = Math.max(max, length);
dfs(node.left, 'l', last !== 'l' ? length + 1 : 1);
dfs(node.right, 'r', last !== 'r' ? length + 1 : 1);
}
dfs(root, 'l', 0);
return max;
};