Breaking a problem into sub-problems

This is a problem that seems to be suitable for breaking into three clear parts https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

1123. Lowest Common Ancestor of Deepest Leaves

Medium

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children
• The depth of the root of the tree is 0, and if the depth of a node is d, the depth of each of its children is d+1.
• The lowest common ancestor of a set S of nodes is the node A with the largest depth such that every node in S is in the subtree with root A.

Example 1:

Input: root = [1,2,3]
Output: [1,2,3]
Explanation: 
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".

Example 2:

Input: root = [1,2,3,4]
Output: [4]

Example 3:

Input: root = [1,2,3,4,5]
Output: [2,4,5]

Constraints:

• The given tree will have between 1 and 1000 nodes.
• Each node of the tree will have a distinct value between 1 and 1000.

There are three distinct parts of the problem:
1) Map each unique number to its corresponding node
2) Then, for each path in the tree, build a map <path len, path>. You will need to encode the path somehow (use your favorite encoder)
3) Now, do a linear search of all the max paths, looking for the first diff. Keep track of the latest common number, because that's what you'll return

Put it all together, works. Cheers, ACC.

public class Solution
{
    public TreeNode LcaDeepestLeaves(TreeNode root)
    {
        //Map numbers to nodes
        Hashtable numberToNode = new Hashtable();
        MapNumberToNode(root, numberToNode);

        //Max paths
        Hashtable mapPath = new Hashtable();
        int max = 0;
        MapPaths(root, "", 0, mapPath, ref max);

        //LCA number
        int lcaNumber = LcaGivenPaths((List<string>)mapPath[max]);

        return (TreeNode)numberToNode[lcaNumber];
    }

    private int LcaGivenPaths(List<string> paths)
    {
        int maxLen = 0;
        for (int i = 0; i < paths.Count; i++)
        {
            maxLen = Math.Max(maxLen, paths[i].Length);
        }

        int previousNumber = 0;
        int currentNumber = 0;
        for (int i = 0; i < maxLen; i++)
        {
            bool foundDiff = false;
            char c = '*';
            for (int j = 0; j < paths.Count; j++)
            {
                if (i < paths[j].Length)
                {
                    if (c == '*')
                    {
                        c = paths[j][i];
                    }
                    else
                    {
                        if (paths[j][i] != c)
                        {
                            foundDiff = true;
                            break;
                        }
                    }
                }
            }

            if (foundDiff)
            {
                return previousNumber;
            }
            else
            {
                if (c == '@')
                {
                    previousNumber = currentNumber;
                    currentNumber = 0;
                }
                else
                {
                    currentNumber = 10 * currentNumber + (int)(c - '0');
                }
            }
        }

        return currentNumber;
    }

    private void MapPaths(TreeNode node, string path, int count, Hashtable mapPath, ref int max)
    {
        if (node == null) return;

        if (node.left == null && node.right == null)
        {
            count++;
            max = Math.Max(max, count);

            path += node.val.ToString();

            if (!mapPath.ContainsKey(count))
            {
                List<string> list = new List<string>();
                list.Add(path);
                mapPath.Add(count, list);
            }
            else
            {
                List<string> list = (List<string>)mapPath[count];
                list.Add(path);
            }

            return;
        }

        if (node.left != null)
        {
            MapPaths(node.left, path + node.val.ToString() + "@", count + 1, mapPath, ref max);
        }
        if (node.right != null)
        {
            MapPaths(node.right, path + node.val.ToString() + "@", count + 1, mapPath, ref max);
        }
    }

    private void MapNumberToNode(TreeNode node, Hashtable numberToNode)
    {
        if (node == null) return;
        numberToNode.Add(node.val, node);
        MapNumberToNode(node.left, numberToNode);
        MapNumberToNode(node.right, numberToNode);
    }
}