1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    // Adjacency list: maps each tree node to its neighbors (parent + children).
18    private final Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
19    // Tracks nodes currently on the DFS path to prevent revisiting them.
20    private final Set<TreeNode> visited = new HashSet<>();
21
22    /**
23     * Computes the maximum path sum by treating the binary tree as an
24     * undirected graph and exploring the best path starting from every node.
25     *
26     * @param root the root of the binary tree
27     * @return the maximum achievable path sum
28     */
29    public int maxSum(TreeNode root) {
30        // Build the undirected adjacency representation of the tree.
31        dfs(root, null);
32
33        int ans = Integer.MIN_VALUE;
34        // Try starting a path from each node and keep the global maximum.
35        for (TreeNode node : graph.keySet()) {
36            ans = Math.max(ans, dfs2(node));
37            visited.clear();
38        }
39        return ans;
40    }
41
42    /**
43     * Builds the adjacency list by linking each node to its parent
44     * and to both of its children.
45     *
46     * @param node   the current node being processed
47     * @param parent the parent of the current node (null for the root)
48     */
49    private void dfs(TreeNode node, TreeNode parent) {
50        if (node == null) {
51            return;
52        }
53        // Ensure the current node has an entry in the graph.
54        graph.computeIfAbsent(node, key -> new ArrayList<>());
55        // Connect the node to its parent and children.
56        graph.get(node).add(parent);
57        graph.get(node).add(node.left);
58        graph.get(node).add(node.right);
59
60        // Recurse into the children, passing the current node as their parent.
61        dfs(node.left, node);
62        dfs(node.right, node);
63    }
64
65    /**
66     * Performs a DFS from the given node to find the maximum sum of a simple
67     * path (no repeated nodes) extending from it.
68     *
69     * @param node the current node in the traversal
70     * @return the best path sum reachable starting from this node
71     */
72    private int dfs2(TreeNode node) {
73        // Skip null nodes or nodes already on the current path.
74        if (node == null || visited.contains(node)) {
75            return 0;
76        }
77        // Mark the node as part of the current path.
78        visited.add(node);
79
80        int result = node.val;
81        int best = 0;
82        // Explore all neighbors and keep the most valuable extension.
83        for (TreeNode next : graph.getOrDefault(node, Collections.emptyList())) {
84            best = Math.max(best, dfs2(next));
85        }
86
87        // Backtrack: remove the node so other paths can use it.
88        visited.remove(node);
89        return result + best;
90    }
91}
92

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int maxSum(TreeNode* root) {
15        // adjacency list: maps each node to its neighbors (parent, left child, right child)
16        unordered_map<TreeNode*, vector<TreeNode*>> adjacency;
17        // tracks visited node values during a single path traversal to avoid revisiting
18        unordered_set<int> visited;
19
20        // Build an undirected graph from the binary tree.
21        // For each node, record its parent and its two children as neighbors.
22        auto buildGraph = [&](this auto&& buildGraph, TreeNode* node, TreeNode* parent) -> void {
23            if (!node) return;
24            adjacency[node].push_back(parent);
25            adjacency[node].push_back(node->left);
26            adjacency[node].push_back(node->right);
27            buildGraph(node->left, node);
28            buildGraph(node->right, node);
29        };
30
31        // Compute the maximum path sum starting from the given node.
32        // It explores neighbors recursively, marking values as visited to
33        // prevent cycles within the current path.
34        auto maxPathFrom = [&](this auto&& maxPathFrom, TreeNode* node) -> int {
35            // Stop if the node is null or its value is already on the current path.
36            if (!node || visited.count(node->val)) return 0;
37            visited.insert(node->val);
38            int current = node->val;
39            int bestNeighbor = 0;
40            // Extend the path through the best-scoring neighbor.
41            for (auto next : adjacency[node]) {
42                bestNeighbor = max(bestNeighbor, maxPathFrom(next));
43            }
44            // Backtrack: remove this value so other paths can reuse it.
45            visited.erase(node->val);
46            return current + bestNeighbor;
47        };
48
49        // Construct the graph starting from the root (root has no parent).
50        buildGraph(root, nullptr);
51
52        // Try every node as a potential starting point and keep the best path sum.
53        int ans = INT_MIN;
54        for (auto& [node, _] : adjacency) {
55            ans = max(ans, maxPathFrom(node));
56            visited.clear();
57        }
58        return ans;
59    }
60};
61

1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 *     val: number
5 *     left: TreeNode | null
6 *     right: TreeNode | null
7 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.left = (left===undefined ? null : left)
10 *         this.right = (right===undefined ? null : right)
11 *     }
12 * }
13 */
14
15// Adjacency map: each node maps to its neighbors (parent, left child, right child)
16let graph: Map<TreeNode, (TreeNode | null)[]>;
17
18// Set tracking values currently on the active path (to avoid revisiting by value)
19let visited: Set<number>;
20
21/**
22 * Build an undirected graph from the binary tree.
23 * For each node, record its parent and both children as neighbors.
24 * @param node - the current tree node
25 * @param parent - the parent of the current node
26 */
27function buildGraph(node: TreeNode | null, parent: TreeNode | null): void {
28    if (!node) return;
29    // Initialize the neighbor list for this node if absent
30    if (!graph.has(node)) graph.set(node, []);
31    // Connect this node to its parent and its two children
32    graph.get(node)!.push(parent, node.left, node.right);
33    // Recurse into children, passing the current node as their parent
34    buildGraph(node.left, node);
35    buildGraph(node.right, node);
36}
37
38/**
39 * Compute the maximum path sum extending from the given node,
40 * choosing the single best neighbor branch and avoiding values
41 * already present on the current path.
42 * @param node - the current node being explored
43 * @returns the best sum reachable starting at this node
44 */
45function findMaxPath(node: TreeNode | null): number {
46    // Stop if the node is null or its value is already on the path
47    if (!node || visited.has(node.val)) return 0;
48
49    // Mark this node's value as part of the current path
50    visited.add(node.val);
51
52    const currentValue = node.val;
53    let bestBranch = 0;
54
55    // Explore all neighbors and keep the largest extension
56    for (const neighbor of graph.get(node) || []) {
57        bestBranch = Math.max(bestBranch, findMaxPath(neighbor));
58    }
59
60    // Backtrack: remove this node's value before returning
61    visited.delete(node.val);
62
63    return currentValue + bestBranch;
64}
65
66/**
67 * Find the maximum path sum over the tree, treating it as an
68 * undirected graph and ensuring no value repeats along a path.
69 * @param root - the root of the binary tree
70 * @returns the maximum achievable path sum
71 */
72function maxSum(root: TreeNode | null): number {
73    // Reset global state for this invocation
74    graph = new Map<TreeNode, (TreeNode | null)[]>();
75    visited = new Set<number>();
76
77    // Construct the adjacency representation of the tree
78    buildGraph(root, null);
79
80    let answer = -Infinity;
81
82    // Try starting a path from every node and keep the best result
83    for (const node of graph.keys()) {
84        answer = Math.max(answer, findMaxPath(node));
85        visited.clear();
86    }
87
88    return answer;
89}
90