[LeetCode] 1372. Longest ZigZag Path in a Binary Tree

1. Question

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

2. Thoughts

3. Tips learned

4. My solution

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        self.max_count = 0

        def dfs(node, is_right, count):
            if not node:
                return

            self.max_count = max(self.max_count, count)
            dfs(node.right, True, 1 if is_right else count + 1)
            dfs(node.left, False, count + 1 if is_right else 1)

        dfs(root.right, True, 1)
        dfs(root.left, False, 1)

        return self.max_count

58/58 cases passed (300 ms)
Your runtime beats 63 % of python3 submissions
Your memory usage beats 40.55 % of python3 submissions (64.1 MB)

5. AI Solution and Improvements

Your solution to find the number of paths in a binary tree that sum up to a target value involves a depth-first search (DFS) with a somewhat complex approach to tracking and counting the sums. While your approach is interesting, it can be significantly optimized both in terms of space and time complexity.

Suggested Improvement

A more efficient approach is to use a recursive DFS function that keeps track of the current path sum and a dictionary to store the number of times each sum has occurred so far. This method is more efficient as it avoids creating and merging lists at each node, which can be costly in terms of time and memory.

Here's the revised code:

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.count = 0
        cache = {0: 1}

        def dfs(node, current_sum):
            if not node:
                return

            # Update the current sum and the number of paths that reach this sum
            current_sum += node.val
            old_sum = current_sum - targetSum
            self.count += cache.get(old_sum, 0)

            # Update the cache with the current sum
            cache[current_sum] = cache.get(current_sum, 0) + 1

            # Recursively call on children
            dfs(node.left, current_sum)
            dfs(node.right, current_sum)

            # Remove the current sum from the cache when going back up the recursion tree
            cache[current_sum] -= 1

        dfs(root, 0)
        return self.count

Explanation

• Recursive DFS: The dfs function traverses the tree, keeping track of the cumulative sum of the node values from the root to the current node.

• Path Sum Counting: When the difference between the current cumulative sum and the target sum has been seen before, it means there's a path that sums up to the target sum. The count of such paths is incremented accordingly.

• Cache: A dictionary (cache) is used to keep track of how many times each sum has occurred. This is crucial for efficiently finding the number of paths that add up to the target sum.

• Updating and Cleaning Up the Cache: After each node visit, the current sum is added to the cache. When the recursion goes back up the tree (after visiting left and right children), the current sum is decremented in the cache to ensure only the sums of the current paths are counted.

Benefits of the Improved Solution

• Efficiency: This approach is more efficient in terms of both time and space. It avoids the overhead of creating and managing lists of sums at each node.
• Simplicity: The logic is simpler and more direct, focusing on the cumulative sums and the differences that match the target sum.
• Scalability: The solution is more scalable and can handle larger trees more effectively.