Memoization II

I wrote about memoization many years ago. Memoization is a glorified caching. Here is when it can come handy: https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/

1372. Longest ZigZag Path in a Binary Tree

Medium

Given a binary tree root, 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 then move to the right child of the current node otherwise move to the left child.
• Change the direction from right to left or right to left.
• Repeat the second and third step 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,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

Constraints:

• Each tree has at most 50000 nodes..
• Each node's value is between [1, 100].

Accepted

2,271

Submissions

4,951

I followed the hint in this problem, but unfortunately the solution timed out. In order to work around the timeout, memoization (remembering previous solutions) came handy. This is simply the code for memoization, highlighted below:

private int LongestZigZag(TreeNode node,
                            bool direction /*false: left, true: right*/)
{
    if (node == null) return 0;
    string key = node.GetHashCode().ToString() + direction.ToString();
    if (cache.ContainsKey(key)) return (int)cache[key];
    int val = 1 + LongestZigZag(direction ? node.right : node.left, !direction);
    cache.Add(key, val);
    return val;
}

Basically for each node and each direction (L or R), cache the solution and reuse it. Notice that I used GetHashCode() to create a key for each node, albeit this is strictly not recommended due to the possibility of collisions. But in this case, probably because the input wasn't massive, it worked. Cheers, ACC.

public class Solution

{

    private Hashtable cache = new Hashtable();

    public int LongestZigZag(TreeNode root)

    {

        int retVal = 0;

        Process(root, ref retVal);

        return retVal > 0 ? retVal - 1 : retVal;

    }

    private void Process(TreeNode node, ref int max)

    {

        if (node == null) return;

        max = Math.Max(max, Math.Max(LongestZigZag(node, true), LongestZigZag(node, false)));

        Process(node.left, ref max);

        Process(node.right, ref max);

    }

    private int LongestZigZag(TreeNode node,

                                bool direction /*false: left, true: right*/)

    {

        if (node == null) return 0;

        string key = node.GetHashCode().ToString() + direction.ToString();

        if (cache.ContainsKey(key)) return (int)cache[key];

        int val = 1 + LongestZigZag(direction ? node.right : node.left, !direction);

        cache.Add(key, val);

        return val;

    }

}