题目描述

题目链接

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例1：
lc124_1

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例2：
lc124_2

1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

算法1

(遍历) O(n2)O(n^2)

对于这道问题，我们需要思考的是：

  • 一个节点的最大路径和到底如何计算？
    根据树的递归特性，我们可以知道：一个节点的最大路径，一定是经过其左子树、右子树的最大路径，在加上当前路径大小的值

需要注意的是：

  • 当左、右子树某个最大路径为负数时，我们可以不走这条路径，那么可以将路径与 0 取最大值

这样，我们遍历所有的节点，找到经过所有结点的最大路径值，这样我们就可以得到整个树中的最大路径值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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 ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);

        return ans;
    }

    int dfs(TreeNode* root)
    {
        if( !root) return 0;

        int left = max(0, dfs(root->left)); // 经过当前左子树根节点的最大路径值
        int right = max(0, dfs(root->right)); // 经过右子树根节点的最大路径值
        ans = max(ans, left + right + root->val); // 那么经过当前节点的最大路径就为左右子树的最大路径加上当前节点的值
        return max(left, right) + root->val; // 向上层返回当前经过当前节点的最大路径值，为其左子树的最大路径与右子树最大路径的最大值与当前节点值得和
    }
};