题解 | #二叉树的最大路径和#

DFS
对每一个节点求路径和贡献最大值（只左侧子树/右侧子树，维持一条路），总路径为左侧+右侧+该节点

  class Solution{
      public:
          /**
           *
           * @param root TreeNode类
           * @return int整型
           */
        int maxSum = INT32_MIN;
          int maxPathSum(TreeNode* root) {
              // write code here
              dfs(root);
              return maxSum;
          }


          int dfs(TreeNode* root){
              if(root == nullptr){
                  return 0;
              }
              int leftMax = dfs(root->left);
              int rightMax = dfs(root->right);
              maxSum = max(maxSum,max(leftMax,max(rightMax,max(leftMax+rightMax,0)))+root->val);
              return max(leftMax,max(rightMax,0))+root->val;
          }
  };