Actual path in maximum path sum in binary tree

Question

I'm trying to store and print the actual path in the problem of finding maximum path sum in a binary tree. I already know how to find the maximum path sum (below), but how can we add a snippet to output the actual path?

private int maxSum;
public int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
findMax(root);
return maxSum;
}

private int findMax(TreeNode p) {
if (p == null) return 0;
int left = findMax(p.left);
int right = findMax(p.right);
maxSum = Math.max(p.val + left + right, maxSum);
int ret = p.val + Math.max(left, right);
return ret > 0 ? ret : 0;
}

Answer 1

May you can try this.

static class Node {
        
        int pathSum;
        List<Integer> path;
        
        Node(int pathSum) {
            this.pathSum = pathSum;
            this.path = new ArrayList<>();
        }
    }
    
    
    public List<Integer> maxPathSum(TreeNode root) {
        
        solve(root);
        return maxPathTrace;
        
    }
    
    
    int maxPath = Integer.MIN_VALUE;
    List<Integer> maxPathTrace = new ArrayList<>();

    public Node solve(TreeNode root) {

        if ( root == null) return new Node(0);
                
        Node leftNode = solve(root.left);
        Node rightNode = solve(root.right);
        
        int leftGain = Math.max(leftNode.pathSum, 0);
        int rightGain = Math.max(rightNode.pathSum, 0);
        
        int resultGain = leftGain + rightGain + root.val;
       
        // calculate max path and note it down    
        if ( resultGain > maxPath) {
            maxPathTrace.clear();
                if ( leftNode.pathSum >= 0) {
                    maxPathTrace.addAll(leftNode.path);
                }
                maxPathTrace.add(root.val);
                if ( rightNode.pathSum >= 0) {
                    maxPathTrace.addAll(rightNode.path);
                }
        }
         maxPath = Math.max(resultGain, maxPath);
        
        
        //calculate return path
        Node resultNode = new Node(Math.max(leftGain + root.val , rightGain + root.val));
        if ( leftGain > rightGain ) {
            if ( leftNode.pathSum >= 0) {
                resultNode.path.addAll(leftNode.path);
            }
            resultNode.path.add(root.val);
        } else {
             resultNode.path.add(root.val);
            if ( rightNode.pathSum >= 0) {
               resultNode.path.addAll(rightNode.path);
            }   
        }
        
        
        return resultNode;
        
    }