L124 二叉树中的最大路径和

树

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

解：递归思想，找出左右的路径哪个和大(正数)，返回max(left,right)+root->val

int res = INT_MIN;
    int maxPathSum(TreeNode* root) {
        getMax(root);
        return res;       
    }
    int getMax(TreeNode *root){
        if(root == NULL) return 0;
        int left = max(0,getMax(root->left));
        int right = max(0,getMax(root->right));
        res = max(res, root->val+left+right);
        return max(left,right)+root->val;
    }