1372. Longest ZigZag Path in a Binary Tree

[songyy5517]

You are given the root of a binary tree. A ZigZag path for a binary tree is defined as follow:

• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
• Change the direction from right to left or from left to right.
• Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0). Return the longest ZigZag path contained in that tree.

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3:

Input: root = [1]
Output: 0

Intuition The problem is to find the longest ZigZag path which includes the nodes whose direction is different from its father and son nodes. So a simple idea is searching the entire tree with DFS. The key here is to determine whether a path is a ZigZag path. To achieve this, we define an additional boolean variable in the DFS method to indicate whether the current node is the right node of its father. Then we update the length of ZigZag paths based on this variable.

[songyy5517]

Approach: DFS with a Boolean variable

1. Exception handling;
2. Define a global variable to record the maximum path length;
3. DFS(TreeNode root, int path_len, boolean right) : Search the entire tree with DFS:
   • Update the global maxium path length;
   • Based on the right variable, update the current path length;
4. Return the global maximum path length.

Complexity Analysis

• Time complexity: $O(N)$ , searching the whole tree takes $O(N)$ time;
• Space complexity: $O(N)$ , the binary tree would degenerate into a linked list in the worst case, which occupies the space of $O(N)$ .

[songyy5517]

/**
 * 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 {
    int max_len = 0;

    public int longestZigZag(TreeNode root) {
        // Intuition: DFS
        // 1. Exception Handling
        if (root == null)
            return 0;

        dfs(root.left, 1, false);
        dfs(root.right, 1, true);

        return max_len;
    }

    // right: whether the current node is a right son of its father node
    void dfs(TreeNode root, int path_len, boolean right){
        if (root == null)
            return ;

        max_len = Math.max(max_len, path_len);

        if (right){
            dfs(root.left, path_len + 1, false);
            dfs(root.right, 1, true);
        }
        else {
            dfs(root.left, 1, false);
            dfs(root.right, path_len + 1, true);
        }

    }
}

[songyy5517]

2024/6/4