[이차수 9] 이차수 중 임의의 두 노드의 최대 경로와

[문제] 임의의 두 노드를 주의하세요. 잎만 잎에 닿거나 잎을 따라가는 것이 아닙니다.노드 값이 음수인 상황을 특별히 고려하다.
【code】
leetcode의 첫 번째 문제는 버그가 세 번이나 걸려서야 통과되었다.
함수 maxNode는 sum의 초기 값으로 노드의 최대 값을 되돌려줍니다.
함수 maxHandSum은 현재 노드를 루트 노드로 하고 얻은 최대 합을 되돌려줍니다. 특히 마지막 if문장에 주의하여 마이너스 공헌을 가진 서브트리를 가지치기합니다.
다음 사항에 유의하십시오.
1. 단독 노드의 트리-3, 지나치지 않았습니다. 왜냐하면 처음에 저는 단순하게sum를 0으로 초기화했고 최대sum 출력도 0으로 초기화했기 때문입니다.
2, 9 6 - 3 # - 6 2 # 2 # - 6 - 6, 아니 가지치기
내 스팸 코드:

 int maxNode(TreeNode *root, int &sum) {
        if (root == NULL)
            return 0;
        if (root->val > sum)
            sum = root->val;
        maxNode(root->left, sum);
        maxNode(root->right, sum);
        return 0;
            
    }

    int maxHandSum(TreeNode *root, int &sum) {
        if (root == NULL)
            return 0;
        int maxleft = maxHandSum(root->left,sum);
        int maxright = maxHandSum(root->right,sum);
        int newsum1 = maxleft + maxright + root->val;
        int newsum2 = (maxleft > maxright ? maxleft : maxright) + root->val;
        if (newsum1 > sum)
            sum = newsum1;
        if (newsum2 > sum)
            sum = newsum2;
        if (newsum2 < root->val)
            return root->val;
        else 
            return newsum2;
    }
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int sum = root->val;
        maxNode(root,sum);
//        int sum = -10;
        maxHandSum(root, sum);
        return sum;
    }

우박 인물의 코드:
Three case:
Left tree path plus the current root.
Right tree path plus the current root.
The path passes through the root and hence one needs to consider the left path + current root + right path.
잎 노드에서 위로 계산하기:
A, csum은 이 노드를 뿌리 노드로 하는 왼쪽 나무, 오른쪽 나무, only 이 노드를 가리키며 이 세 가지의 최대치를 고찰하여 상기 1, 2 두 가지 상황을 고찰한다
B, maxsum은 이전의 maxsum, csum, 이 노드를 거친sum를 가리키며 상술한 세 번째 상황을 고찰한다
     
   

int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int csum;
        int maxsum = INT_MIN;
        maxPathSumHelper(root, csum, maxsum);
        return maxsum;

    }
    void maxPathSumHelper(TreeNode *node, int &csum, int &maxsum) {
        if (!node) {
            csum = 0;
            return;
        }
        int lsum = 0, rsum = 0;
        maxPathSumHelper(node->left, lsum, maxsum);
        maxPathSumHelper(node->right, rsum, maxsum);
        csum = max(node->val, max(node->val + lsum, node->val + rsum));
        maxsum = max(maxsum, max(csum, node->val + lsum + rsum));
    }