leetcode124. 二叉树中的最大路径和（DFS）

二叉树dfs操作

题目描述

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。
该路径至少包含一个节点，且不一定经过根节点。

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

思路

• 利用一个子函数，求出每个节点最大深度路径和（做法类似求树的深度）

  • 注意，因为节点中的值可能为负数，所以最大深度路径和不一定都会到达叶子
  • 同样，最大深度路径和也可能为负数，此时应该返回 0

• 接着对每个节点，经过该节点的最大路径和为

  该节点的值 + 左子树的最大深度路径和 + 右子树的最大深度路径和

• 空树的最大路径和应该为负无穷（作为递归基）；

C++

代码实现：

class Solution {
    const int inf = 0x3f3f3f3f;
    int ret = -inf;

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

        int l_sum = max(0, maxDeepSum(node->left));
        int r_sum = max(0, maxDeepSum(node->right));

        ret = max(ret, node->val + l_sum + r_sum);
        return node->val + max(l_sum, r_sum);
    }
public:
    int maxPathSum(TreeNode* root) {
        maxDeepSum(root);
        return ret;
    }
};