1372. Longest ZigZag Path in a Binary Tree

Description

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.

Intuition

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.

Approach

1. Depth-First Search (DFS): - We initiate a DFS traversal starting from the root node. - At each node, we keep track of the direction from which we arrived (left or right) and the length of the current zigzag path. - If we move in the same direction as the last move, the zigzag path length is reset. If we change direction, we increment the length. - The maximum zigzag path length encountered during the traversal is stored and updated at each step.
2. Termination: - The traversal ends when all nodes have been visited. The maximum recorded zigzag length is returned as the result.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the tree. Each node is visited once during the DFS traversal.

Space Complexity:

O(H), where H is the height of the tree. This space is used by the recursive stack during the DFS.

Code

C++

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;
    }
};

Python

# 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

Java

/**
 * 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;
    }
}

JavaScript

/**
 * 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;
};