LeetCode 124: Binary Tree Maximum Path Sum

Question 1

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   3Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]   -10   / \  9  20    /  \   15   7Output: 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

642667918001552

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

Question 2

There's not much to say about your answer, it looks fine! One could quibble over the names of variables, maybeleft andright could be namedleft_sum andright_sum for example, and you could've usedauto for the type of those two variables. But other than that I think there is nothing that can be improved.

Question 3

Not sure why you decided to usestd::int_fast64_t over the commonint 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;

Question 4

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)

Question 5

Or create a named objectstatic constexpr std::int_fast64_t fast_zero(0);

G. Sliepen 69.5k3 gold badges75 silver badges180 bronze badges · Accepted Answer · 2020-07-22 22:51:16Z

There's not much to say about your answer, it looks fine! One could quibble over the names of variables, maybeleft andright could be namedleft_sum andright_sum for example, and you could've usedauto for the type of those two variables. But other than that I think there is nothing that can be improved.

Movatterモバイル変換

Stack Exchange Network

LeetCode 124: Binary Tree Maximum Path Sum

Problem

Example 1:

Example 2:

Inputs

Outputs

Code

References

2 Answers2

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS