【leetcode】124. 두 갈래 나무의 최대 경로와
4085 단어 LeetCode
제목
비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.
본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다.
생각
이 제목은 처음에 나는 생각이 없어서 어리둥절한 표정이었다.처음에는 검색해서 해결하자고 생각했지만 결과가 반드시 루트를 거치는 것은 아니었다. 그리고 나는 생각이 없었다.그럼 문제를 간소화해라. 만약 답안이 반드시 뿌리 노드를 거친다면, 귀속 구해는 매우 간단하다.그러나 귀속 구해 과정 중의 함수의 정의를 깊이 연구해 보면 이 함수는 이 노드를 루트 노드로 하는 가장 큰 값을 구할 수 있을 뿐이다.문제는 하위 문제를 어떻게 원래의 문제로 통합시킬 것인가에 있다.가장 좋은 것은 두 가지 상황이 있는데,
+ + 에서 나온 최우선은 그 부 노드의 최우선에 속하지 않는다. + 만이 부모 노드에 속하는 가장 좋은 것을 포함한다.그러면 이런 비부 노드의 가장 좋은 포함 상황
+ + 과 같이 우리는 전역 변수로 저장할 수 있다.그러면 코드가 쉽게 나와요.코드
class Solution {
private:
int ret = INT_MIN;
int getMax(TreeNode * root) {
if (root == nullptr) return 0;
int left = max(0, getMax(root->left));
int right = max(0, getMax(root->right));
ret = max(ret, root->val + left + right);
return max(left, right) + root->val;
}
public:
int maxPathSum(TreeNode* root) {
return max(ret, getMax(root));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
