leetcode124：二叉树中的最大路径和

题目链接

leetcode

题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
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) {}
};

const int NULL_NODE = -1001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现
    
    树中每条路径，都存在一个离根结点最近的点，把它记为割点，用割点可以将整条路径分为两部分。
    从该结点向左子树延伸的路径，从该结点向右子树延伸的部分，两部分都是自上而下延伸。
    递归遍历整棵树（后序遍历），递归时维护从每个结点开始向下延伸的最大路径和。
    对于每个点，递归计算完左右子树后，得到以这个点为割点的最大路径。
    维护从这个点向下延伸的最大路径，从左右子树的路径中选择权值大的一条延伸。

    时间复杂度：O(n)
        其中 n 是二叉树中的结点个数。
        每个结点仅会遍历一次，所以时间复杂度是 O(n)。
    空间复杂度：O(n)
        主要取决于递归调用层数，最大层数等于二叉树的高度。
        最坏情况下，二叉树的高度等于二叉树中的结点个数。
*/
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        // 计算左右子树的最大路径和
        int left = max(0, dfs(node->left));
        int right = max(0, dfs(node->right));
        // 更新全局最大值
        res = max(res, node->val + left + right);
        
        return node->val + max(left, right); 
    }

private:
    int res = INT_MIN;
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> root_cases = {
        {1,2,3},
        {-10,9,20,NULL_NODE,NULL_NODE,15,7}
    };

    for (const auto& nums : root_cases) {
        cout << "Input: ";
        printArray(nums);

        // 创建二叉树
        TreeNode* root = createTree(nums);
        // 计算最大路径和
        int result = solution.maxPathSum(root);
        cout << "Output: " << result << endl;

        // 释放内存
        deleteTree(root);
    }

    return 0;
}