Problem
Given the root of a binary tree, a ZigZag path starts at any node and follows these rules: if the previous move was to the left, the next move must be to the right, and if the previous move was to the right, the next move must be to the left.The length of a ZigZag path is the number of edges in the path. Return the length of the longest ZigZag path in the tree.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
root:
1
/ \
1 1
/ \
1 1
\
1Output
3Example 2
Input
root:
1
/
1
/
1Output
1Solution
This solution uses Depth-First Search (DFS). For every node, we maintain two values: the length of the ZigZag path if the next move is to the left, and the length if the next move is to the right.If we move left, the next move must be right, so the left ZigZag length is calculated from the right direction of the child. Similarly, if we move right, the next move must be left.
class Solution {
int max = 0;
public int longestZigZag(TreeNode root) {
dfs(root, true, 0);
dfs(root, false, 0);
return max;
}
private void dfs(TreeNode node, boolean isLeftNode, int length) {
if (node == null) {
return;
}
max = Math.max(max, length);
if (isLeftNode) {
dfs(node.left, true, 1);
dfs(node.right, false, length + 1);
} else {
dfs(node.right, false, 1);
dfs(node.left, true, length + 1);
}
}
}Complexity
Each node is visited a constant number of times, so the time complexity isO(n), where n is the number of nodes in the binary tree.
The DFS recursion uses space proportional to the height of the tree, so the extra space complexity is
O(h), where h is the height of the tree.