This is a Graph Problem - Not a Tree Problem! Part IV

I think this problem had everything: hashtables, hashsets, recursive DFS and non-recursive DFS and even applications of the dangerous .GetHashCode(), which I don't like but sometimes it is good enough when the constraints are limited, which is the case of this problem.

But the problem isn't a tree problem - it is a graph one. Convert the tree to a graph (needed because you'll be navigating up and down the tree), and that's where I'm using .GetHashCode() to uniquely identify the nodes (worked), then for each node (non-recursive DFS) perform a search (recursive DFS) looking for the max path, traversing only in the case of unique numbers. Notice that you need to keep going even if you find a -ve node since there might be a larger unvisited number behind that node. Code is down below, cheers, ACC.

Maximum Distinct Path Sum in a Binary Tree - LeetCode

You are given the root of a binary tree, where each node contains an integer value.

A valid path in the tree is a sequence of connected nodes such that:

• The path can start and end at any node in the tree.
• The path does not need to pass through the root.
• All node values along the path are distinct.

Return an integer denoting the maximum possible sum of node values among all valid paths.

 

Example 1:

Input: root = [2,2,1]

Output: 3

Explanation:

• The path 2 → 2 is invalid because the value 2 is not distinct.
• The maximum-sum valid path is 2 → 1, with a sum = 2 + 1 = 3.

Example 2:

Input: root = [1,-2,5,null,null,3,5]

Output: 9

Explanation:

• The path 3 → 5 → 5 is invalid due to duplicate value 5.
• The maximum-sum valid path is 1 → 5 → 3, with a sum = 1 + 5 + 3 = 9.

Example 3:

​​​​​​​

Input: root = [4,6,6,null,null,null,9]

Output: 19

Explanation:

• The path 6 → 4 → 6 → 9 is invalid because the value 6 appears more than once.
• The maximum-sum valid path is 4 → 6 → 9, with a sum = 4 + 6 + 9 = 19.

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -1000 <= Node.val <= 1000​​​​​​​

public class Solution {
    public int MaxSum(TreeNode root)
    {
        Hashtable graph = new Hashtable();

        CreateGraphFromTree(root, null, graph);

        int maxVal = Int32.MinValue;
        Stack stack = new Stack();
        stack.Push(root);
        while (stack.Count > 0)
        {
            TreeNode currentNode = stack.Pop();
            int nodeMaxPathSum = Int32.MinValue;
            HashSet numbersUsed = new HashSet();
            numbersUsed.Add(currentNode.val);
            MaxUniquePath(currentNode, graph, numbersUsed, currentNode.val, ref nodeMaxPathSum);
            maxVal = Math.Max(maxVal, nodeMaxPathSum);

            if (currentNode.left != null) stack.Push(currentNode.left);
            if (currentNode.right != null) stack.Push(currentNode.right);
        }

        return maxVal;
    }

    private void MaxUniquePath(TreeNode node, Hashtable graph, HashSet numbersUsed, int currentPathSum, ref int maxPathSum)
    {
        if (node == null) return;

        maxPathSum = Math.Max(maxPathSum, currentPathSum);
        int nodeId = node.GetHashCode();

        if (graph.ContainsKey(nodeId))
        {
            HashSet connections = (HashSet)graph[nodeId];
            foreach (TreeNode connectedNode in connections)
            {
                if (!numbersUsed.Contains(connectedNode.val))
                {
                    numbersUsed.Add(connectedNode.val);
                    MaxUniquePath(connectedNode, graph, numbersUsed, currentPathSum + connectedNode.val, ref maxPathSum);
                    numbersUsed.Remove(connectedNode.val);
                }
            }
        }
    }

    private void CreateGraphFromTree(TreeNode node, TreeNode parent, Hashtable graph)
    {
        if (node == null) return;

        graph.Add(node.GetHashCode(), new HashSet());
        HashSet connections = (HashSet)graph[node.GetHashCode()];

        if (parent != null) connections.Add(parent);
        if (node.left != null)
        {
            connections.Add(node.left);
            CreateGraphFromTree(node.left, node, graph);
        }
        if (node.right != null)
        {
            connections.Add(node.right);
            CreateGraphFromTree(node.right, node, graph);
        }
    }
}