트리의 최대 경로 및 Binary Tree Maximum Path Sum

1268 단어
문제: 두 갈래 나무에서 경로를 찾아서 그 경로의 노드 값을 최대로 한다.경로는 임의로 되어 있으며, 첫 번째 끝점은 어디에 있든지 가능하며, 반드시 뿌리 노드를 거쳐야 한다고 요구하지도 않는다.결점 원소는 플러스와 마이너스가 있기 때문에 경로가 길고 큰 것은 아니다.
사고방식 1: 점차 사고방식으로 돌아간다.왼쪽 아이에서 아래로 잎 결점까지의 최대 단방향 경로와 오른쪽 아이에서 아래로 잎 결점까지의 최대 단방향 경로와 두 가지를 더하고 뿌리 노드 자체의 값을 더하면 뿌리 노드를 통과하는 최대 경로와그리고 두 아이의 가장 큰 경로와최대 경로 3개와 에서 최대 값을 선택합니다.
사고방식 2: 사고방식 1 시간 초과.간소화!방법을 강구하여 최대 단방향 경로와 방법을 구하는 과정에서 최치를 찾다.단방향의 최대 귀속을 구하는 과정에서 양방향 경로의 최대 값을 실시간으로 업데이트합니다.
코드:
class Solution {
public:
    
    int maxPathSum(TreeNode *root) {
        if(root == NULL)
            return 0;
        int max = root->val;
        fun(root, max);
        return max;
    }
    
    int fun(TreeNode *root, int &max) // 
    {
        if(root == NULL)
            return 0;
        
        int left = fun(root->left, max);
        if(left < 0) // 
            left = 0;
        int right = fun(root->right, max);
        if(right < 0) // 
            right = 0;
            
        //  root 
        if(left + right + root->val > max)
            max = left + right + root->val;
        
        if(left > right)
            return left + root->val;
        else
            return right + root->val;
        
    }
};
Ionic 5의 이온 탭 스타일 지정
두 갈래 찾기 트리 개념과 관련leetcode 문제

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage