BT-MaximumPathSum

class Solution {
    public int maxPathSum(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        int maxSum = Integer.MIN_VALUE;

        if (root != null) {
            stack.push(root);
        }

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            if (node != null) {
                int currentSum = node.val;

                if (node.left != null) {
                    currentSum += Math.max(node.left.val, 0);
                    stack.push(node.left);
                }

                if (node.right != null) {
                    currentSum += Math.max(node.right.val, 0);
                    stack.push(node.right);
                }

                maxSum = Math.max(maxSum, currentSum);
            }
        }

        return maxSum;
    }
}