두 갈래 트리의 최대 경로 및 -LintCode

설명:
두 갈래 트리를 제시하고 경로와 최대를 찾을 수 있습니다. 경로는 어느 노드에서 시작하고 끝낼 수 있습니다. (경로와 두 노드 사이에 있는 경로의 노드 값의 합)
예:
두 갈래 나무 한 그루를 주시오.

       1
      / \
     2   3

복귀 6 사고방식:
먼저 두 갈래 나무의 노드에 양수도 있고 음수도 존재하며 최대 경로와 소재 경로는 임의의 두 노드의 통로 또는 한 노드 자신임을 고려해야 한다.
그래서 이전 뿌리 노드에서 잎 노드까지의 최대 경로와 구해 방법을 직접 사용할 수 없다.
1. 이 노드가 비어 있으면 반환값은 0입니다.
2. 노드를 가로지르는 왼쪽 트리와 오른쪽 트리, 왼쪽 트리의 최대 비분할 경로(0 이상) + 오른쪽 트리의 최대 비분할 경로(0 이상) + 노드 자체의 값
현재 최대 경로와 Max를 비교하여 큰 수를 Max에 저장합니다.
3. 좌우 노드의 비교적 큰 불분차 경로와 (0보다 큰) + 노드 값을 반환하여 귀속 호출로 사용한다.
AC 코드:

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 
class Solution {
public:
    /*
     * @param root: The root of binary tree.
     * @return: An integer
     */
     
    int maxpath(TreeNode* root,int &Max)
    {
        if(root==NULL)
            return 0;
        int l=maxpath(root->left,Max);
        int r=maxpath(root->right,Max);
        Max=max(Max,max(0,l)+max(0,r)+root->val);
        return max(0,max(l,r))+root->val;
    }

    int maxPathSum(TreeNode * root) {
        // write your code here
        if(root==NULL)
            return 0;
        int Max=INT_MIN;
        maxpath(root,Max);
        return Max;
        
    }
};