题目大意

解题思路

hard就是细节多，来回对着error case调了好几次。思考不全面or懒得思考。
因为节点val可以为负值，所以任何0都要注意，是否会影响到结果。

同时，对二叉树遍历理解的不够透彻，没必要那么麻烦，每个左右子节点，在此之前，也是子树的根节点，也和ans取过max，所以不用再单独考虑了。只需要考虑两件事，当前节点连接左右孩子的路径和返回只能选取一个孩子的路径。

Code

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int ans;
  15.     int dfs(TreeNode* cur) {
  16.         int l, r;
  17.         if (cur->left == nullptr && cur->right == nullptr) {
  18.             ans = max(ans, cur->val);
  19.             return cur->val;
  20.         }
  21.         if (cur->left != nullptr && cur->right == nullptr) {
  22.             l = dfs(cur->left);
  23.             if (l < 0) l = 0;  //discrad
  24.             ans = max(ans, cur->val + l);
  25.             return cur->val + l;
  26.         }  
  27.         if (cur->left == nullptr && cur->right != nullptr) {
  28.             r = dfs(cur->right);
  29.             if (r < 0) r = 0;  //discard
  30.             ans = max(ans, cur->val + r);
  31.             return cur->val + r;
  32.         }
  33.         else {
  34.             l = dfs(cur->left);
  35.             r = dfs(cur->right);
  36.             ans = max(ans, max(l, r));       //不连接，单侧
  39.             if (l < 0) l = 0;
  40.             if (r < 0) r = 0;
  41.             //int tmp = cur->val > 0 ? cur->val : 0;
  43.             ans = max(ans, cur->val + l + r);//连接至少一侧
  45.             return cur->val + max(l, r);
  46.         }    
  48.     }
  49.     int maxPathSum(TreeNode* root) {
  50.         ans = root->val;
  51.         dfs(root);
  52.         return ans;
  53.     }
  54. };