二叉树中的最大路径和

题面

二叉树中的路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径至少包含一个 节点，且不一定经过根节点。

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

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

示例 1：

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

示例 2：

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

提示：

树中节点数目范围是 [1, 3 104]

• -1000 <= Node.val <= 1000

分析

• 显然，这是一个包含重复子问题的动态规划问题

• 定义 dp[i] 表示以 i 为根节点的子树中，经过节点 i 的最大路径和

• dp[i] 由其左右节点的 dp[i->left] 和 dp[i->right] 来决定，dp[i]=max(dp[i->left],dp[i]+dp[i->left],dp[i]+dp[i->right],dp[i]+dp[i->left]+dp[i->right])

• 显然，需要先获取左右子树的信息，然后再向上汇总

• 代码实现如下

  /**
   * 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 sum(TreeNode* root) {
          if (root == nullptr)
              return 0;
          int left = sum(root->left);
          int right = sum(root->right);
          int res = max(max(max(root->val, root->val + left), root->val + right),
                        root->val + left + right);
          std::cout << root->val << " " << left << " " << right << " " << res
                    << std::endl;
          ans = max(ans, res);
          return max(max(root->val, root->val + left), root->val + right);
      }
      int maxPathSum(TreeNode* root) {
          sum(root);
          return ans;
      }
  };

• 这个实现正确吗？显然不正确，这里统计的是以该节点为根节点的子树，但是实际上，假如该节点的父节点也是正的，此时经过该父节点的路径中，最多只可能经过以该节点为根节点的子树的左右一边

• 因此，最终向上层返回结果时，不应该包括把左右子树都计算在内的情况，而是至多只经过该节点的一边的子树，修改后代码如下

  /**
   * 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 sum(TreeNode* root) {
          if (root == nullptr)
              return 0;
          int left = sum(root->left);
          int right = sum(root->right);
          int res = max(max(root->val, root->val + left), root->val + right);
          ans = max(ans, max(res, root->val + left + right));
          return res;
      }
      int maxPathSum(TreeNode* root) {
          sum(root);
          return ans;
      }
  };