124. 두 갈래 나무의 최대 경로와 leetcode

생각:

각 노드에는 다음과 같은 두 가지 상태가 있습니다.

1, 여기까지 올라가야 한다. 이때 이 노드의 왼쪽에서 오른쪽으로 가는 노선이 있을 수 없다. (위로 올라가야 하기 때문에) 이 노드의 x값으로 기록된다.

2, 여기까지 올라가지 않고 이 노드의 y값으로 기록한다.

각 노드의 x값은 max(이 노드의 값, 왼쪽 노드의 x값, 오른쪽 노드의 x값)와 같다

각 노드의 y값은 max(이 노드의 값, 왼쪽 노드의 y값, 오른쪽 노드의 y값, 이 노드의 값 + 왼쪽 노드의 x값, 이 노드의 값 + 왼쪽 노드의 x값, 이 노드의 값 + 왼쪽 노드의 x값, 이 노드의 값 + 오른쪽 노드의 x값) PS: 뒤에 두 개의 빨간색은 일부 노드가 하나의 하위 노드만 있을 수 있기 때문이다.

마지막으로 루트 노드의 max(x, y)를 구하면 된다

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int max_(int x, int y, int w){
        int a = max(x, y);
        return max(a, w); 
    }

    int max_4(int x, int y, int w, int z, int a, int b){
        int c = max(x, y);
        int d = max(w, z);
        int h = max(a, b);
        return max_(c, d, h); 
    }
    vector treeDp(TreeNode* root){
        vectorans;
        if(root->left || root->right){
            vectornode={-9999999,-9999999};
            vectorleftN = root->left?treeDp(root->left):node;
            vectorrightN = root->right?treeDp(root->right):node;

            int nonStop =  root->val + max_(0, rightN.at(0), leftN.at(0));
            int stop = max_4(root->val, leftN.at(1), rightN.at(1), leftN.at(0) + rightN.at(0) + root->val, root->val + leftN.at(0), root->val+rightN.at(0));

            ans.push_back(nonStop);
            ans.push_back(stop);
            return ans;
        }
        ans.push_back(root->val);
        ans.push_back(root->val);
        return ans;
    }
    int maxPathSum(TreeNode* root) {
        vectorans = treeDp(root);
        return max(ans.at(0), ans.at(1));
    }
};