二叉树最大路径和

多么痛的领悟

返回条件写错，调了半小时；初始值写错，调了半小时；递归函数名写错，调了半小时。。。🥱

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxPathSum(TreeNode *root) {
        // write code here
        // 后序遍历，记录左右子树最大的路径节点和
        //    因为需要分别记录左子树和右子树的最大路径和，用循环实现起来比较麻烦
        postOrder(root);
        return maxSum;
    }
    int postOrder(TreeNode *root) {
        if (!root) return 0;
        int left = postOrder(root->left);
        int right = postOrder(root->right);
        int current = root->val;
        if (left > 0) current += left;
        if (right > 0) current += right;
        maxSum = max(maxSum, current);
        // 注意：此处返回的是max(左+中，右+中, 中)，左+右+中不满足题意
        return max(root->val, max(left, right) + root->val);
    }
private:
    int maxSum = INT_MIN;
};