Leetcode 124. Binary Tree Maximum Path Sum

题目

124. Binary Tree Maximum Path Sum

Difficulty: Hard
Total Accepted: 145.3K
Total Submissions: 519.8K

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

解题报告

AC 截图

题目大意

给定一个非空的二叉树，我们需要找到一个路径，使得路径上所有节点的值的和最大。需要注意的是，该路径最少需要包含一个节点，同时这个路径可以不沿着树边「由父到子」的方向走，但是不可以回头。同时，这个路径也不需要经过根结点。

解题思路

很简单的 DFS + 贪心算法就可以求解。因为路径可以不经过根节点，因而任何子过程都有可能产生一个最优解。为了记录这些最优解，我们建立一个全局变量来记录当前的最优解。考虑一条路径，以最上层的节点的视角，其有三种可能的形状：向左/右子树延伸，同时向两个子树延伸，以及一个裸节点。

其中，第一种情况和第三种情况的路径可以被上层节点复用，来构成新的路径；而第二种情况的路径则不能拓展，因为路径不能回头，因而不可能有分叉。因而，在每个子过程中，我们获取左右子树的非第二种情况的最大 sum 的路径，将其中大于 0 的都与节点的值相加，并尝试更新全局最大值。然后选择其中最大的大于零的 sum，与节点的值相加，并返回该值，作为「非第二种情况的最大值」。

然后，不要忘记加上 iostream 的加速装置～我们的最优解就出炉啦：

题解（最优解）

C++ 代码

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int globalMax = 0;

    int maxPathSum(TreeNode* root) {
      globalMax = root->val;

      int maxSum = root->val, temp;

      temp = subtreeMax(root->left);
      if (temp > 0)
        maxSum += temp;
        
      cout << temp;
      
      temp = subtreeMax(root->right);
      if (temp > 0)
        maxSum += temp;

      cout << temp << endl;
        
      if (maxSum > globalMax)
        globalMax = maxSum;

      return globalMax;
    }
    
    int subtreeMax(TreeNode* subroot) {
      if (subroot == nullptr)
        return 0;
      
      int val = subroot->val, temp1, temp2;

      temp1 = subtreeMax(subroot->left);
      temp2 = subtreeMax(subroot->right);
        

      if (temp1 > 0) {
        if (temp2 > 0) {
          if (temp1 > temp2) {
            val += temp1;
            if (val + temp2 > globalMax)
              globalMax = val + temp2;
            return val;
          }
          else {
            val += temp2;
            if (val + temp1 > globalMax)
              globalMax = val + temp1;
            return val;
          }
        }
        else {
          val += temp1;
          if (val > globalMax)
            globalMax = val;
          return val; 
        }
      }
      else if (temp2 > 0) {
        val += temp2;
        if (val > globalMax)
          globalMax = val;
        return val;
      }

      if (val > globalMax)
        globalMax = val;
      return val;
    }
};