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

给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 image.png**

解题思路

后序遍历

  1. class Solution {
  2. public:
  3.     int ans = INT_MIN;
  4.     int maxPathSum(TreeNode* root) {
  5.         oneSideMax(root);
  6.         return ans;
  7.     }
  8.     /*
  9.         后序遍历框架
  10.         全局变量ans记录遍历过程中的最大路径和
  11.     */
  12.     int oneSideMax(TreeNode* root) {
  13.         if( root == nullptr) return 0;
  15.         int left = max(0,oneSideMax(root->left));//负孩子结点无贡献，所以不要负孩子，只要正孩子
  16.         int right = max(0,oneSideMax(root->right));
  18.         ans = max(ans,left + right + root->val);//（左孩子+当前结点+右孩子）构成一条路径，将其与当前记录的最大路径和比较
  19.         return max(left,right) + root->val;//当前结点与左右孩子中的最大者构成一条路径
  20.     }
  21. };