Code Review Asked on December 2, 2021
I’m posting my code for a LeetCode problem. If you’d like to review, please do so. Thank you for your time!
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.
Input: [1,2,3]
1
/
2 3
Output: 6
Input: [-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7
Output: 42
[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]
6
42
66
791
8001552
#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;
}
};
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;
Answered by slepic on December 2, 2021
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.
Answered by G. Sliepen on December 2, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP