TransWikia.com

LeetCode 124: Binary Tree Maximum Path Sum

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!

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

2 Answers

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP