LeetCode 124: Binary Tree Maximum Path Sum

Question

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]
 1
 / \
 2 3
Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]
 -10
 / \
 9 20
 / \
 15 7
Output: 42

Inputs

[1,2,3]
[-10,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7999999,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7]

Outputs

6
42
66
791
8001552

Code

#include <cstdint>
#include <algorithm>
struct Solution {
 int maxPathSum(TreeNode* root) {
 std::int_fast64_t sum = INT_FAST64_MIN;
 depthFirstSearch(root, sum);
 return sum;
 }
private:
 static std::int_fast64_t depthFirstSearch(
 const TreeNode* node,
 std::int_fast64_t& sum
 ) {
 if (!node) {
 return 0;
 }
 const std::int_fast64_t left = std::max(
 (std::int_fast64_t) 0,
 depthFirstSearch(node->left, sum)
 );
 const std::int_fast64_t right = std::max(
 (std::int_fast64_t) 0,
 depthFirstSearch(node->right, sum)
 );
 sum = std::max(sum, left + right + node->val);
 return std::max(left, right) + node->val;
 }
};

References

• Problem

• Discuss

• Solution

Answer 1

There's not much to say about your answer, it looks fine! One could quibble over the names of variables, maybe left and right could be named left_sum and right_sum for example, and you could've used auto for the type of those two variables. But other than that I think there is nothing that can be improved.

Answer 2

Not sure why you decided to use std::int_fast64_t over the common int that is used as the type of the tree nodes values.

But since you did, it would be more idiomatic to do at least:

static_cast<std::int_fast64_t>(0);

instead of

(std::int_fast64_t) 0;

• G. Sliepen: Maybe it is better to avoid casting altogether. Casting implies you started with some different type. You can construct a zero of the proper type directly by writing: std::int_fast64_t(0)
• Loki Astari: Or create a named object static constexpr std::int_fast64_t fast_zero(0);