LeetCode 124. 二叉树中的最大路径和

题目描述

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

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

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42
解析: 路径为
  20
 /  \
15   7

题解

分析

• 一条路径从某个节点出发，先向父节点方向查找若干(0+)步，再向子节点方向查找若干(0+)步。一旦向子节点方向查找，便不能再向父节点方向查找。每条路径都有一个最高节点，也就是路径中其他节点的最低共同祖先节点。
• 采用递归方法 maxPathDown ，1. 计算了这个节点向子节点方向的最大路径和，过程中更新最大路径和。2. 递归完成返回最大路径和。

代码

// C++
int maxPathSum(TreeNode* root) {
    if (!root) {
        return 0;
    }
    int maxNum = root->val;
    maxPathDown(root, maxNum);
    return maxNum;
}
// 返回这个节点向子节点方向的最大路径和
int maxPathDown(TreeNode* root, int& maxNum) {
    if (!root) {
        return 0;
    }
    int left = maxPathDown(root->left, maxNum);
    int right = maxPathDown(root->right, maxNum);
    int sum1 = root->val + left + right; // root为路径的最高节点时
    int sum2 = root->val + max(max(left, right), 0); // root非路径的最高节点时
    maxNum = max(max(sum1, sum2), maxNum);
    return sum2;
}

参考：https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/39775/Accepted-short-solution-in-Java