Иногда, возвращаемое значение и ответ задачи - это разные величины. В таком случае нужно возвращать пару величин или обновлять глобальную переменную, которая и будет ответом.

int globalResult = 0;

int solve(TreeNode root) {
    traverse(root);
    return globalResult;
}

int traverse(TreeNode node, int value) {
    if (node == null) {
        return {base_value};
    }
    int leftResult = 0;
    if ({left_condition}) {
        leftResult = traverse(node.left, {foo(value)});
    }
    int rightResult = 0;
    if ({right_condition}) {
        traverse(node.right, {bar(value)}); 
    }
    globalResult = {g(leftResult, rightResult, node.value)};
    return {f(leftResult, rightResult, node.value)};
}

Смотри также:
1) Шпаргалка по основным алгоритмам для алгоритмического собеседования
2) Шпаргалка по Java для алгоритмического собеседования
3) Разобрал все основные алгоритмы и 47 задач с собеседований на алгоритмы в FAANG