gistfile1.txt

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */


class Solution {
public:
    int maxPathSum(TreeNode* root) {
        max_path(root);
        return max_path_total;
    }

private:
    int max_path_total = -1000;

    void max_path(TreeNode* root)
    {
        struct path_node {
            TreeNode* root;
            int left_max;
            int right_max;
        };
        std::stack<path_node> backtrace{{{root, -1000, -1000}}};
        int child_path_value = -1000;
        for (; !backtrace.empty(); ) {
            if (backtrace.top().root->right == nullptr)
                backtrace.top().right_max = child_path_value;
            else if (backtrace.top().root->left == nullptr)
                backtrace.top().left_max = child_path_value;

            child_path_value = -1000;

            if (backtrace.top().root->left) {
                TreeNode* left = nullptr;
                std::swap(left, backtrace.top().root->left);
                backtrace.push({left, -1000, -1000});
                continue;
            }

            if (backtrace.top().root->right) {
                TreeNode* right = nullptr;
                std::swap(right, backtrace.top().root->right);
                backtrace.push({right, -1000, -1000});
                continue;
            }

            child_path_value = std::max({
                    backtrace.top().root->val,
                    backtrace.top().root->val + backtrace.top().left_max,
                    backtrace.top().root->val + backtrace.top().right_max
                });

            max_path_total = std::max({
                    max_path_total,
                    child_path_value,
                    backtrace.top().root->val + backtrace.top().left_max + backtrace.top().right_max
                });

            backtrace.pop();
        }
    }
};