【leetcode】binary-tree-maximum-path-sum
1853 단어 leetcode
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example: Given the below binary tree,
1
/ \
2 3
Return6.
문제 해결:
두 갈래 나무를 정해서 최대 경로와
경로는 트리의 모든 노드에서 시작하고 끝낼 수 있습니다.
예:
아래의 두 갈래 나무를 주고,
일
/\
2 3
Return6.
내부 질문 목록:
마지막 큰 문제 답안, 가능한 경로의 출처는 다음과 같다.
1. 루트+left 경로;
2. 루트+right 경로;
3. 루트+right 경로+left 경로;
4. 루트 단일한 결점;
코드를 작성하는 과정에서 발생할 수 있는 문제:
1. 결점의 값은 음수일 수 있다.따라서 최대 경로의 초기 값은 최소 값으로 설정해야 한다.
2. 하위 트리 노드에서 되돌아오는 가장 큰 경로와 세 번째 상황이 나타날 수 없음(해결 방법: 우리는 이 형이 가장 큰 경로max를 알고 있는 것을 저장해야 한다).
코드 구현:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include
class Solution {
public:
int _maxPathSum(TreeNode *root,int &max)
{
//
if(root == NULL)
{
return 0;
}
//
int left = _maxPathSum(root->left,max) ;
int right = _maxPathSum(root->right,max) ;
int data = root->val;
int sum = left+right+data;
// max
max = max < (left+data)?(left+data):max;
max = max < (right+data)?(right+data):max;
max = max < data?data:max;
max = max < sum?sum:max;
//
int ret = data;
ret = ret < left+data?left+data:ret;
ret = ret < right +data?right+data:ret;
return ret;
}
int maxPathSum(TreeNode *root) {
if(root == NULL)
{
return 0;
}
// max int
int max = 0x80000000;
_maxPathSum(root,max);
return max;
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
