LeetCode124—Binary Tree Maximum Path Sum
LeetCode124—Binary Tree Maximum Path Sum
원제
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example: Given the below binary tree,
1
/ \
2 3
Return 6.
분석
참조:http://blog.csdn.net/linhuanmars/article/details/22969069이 문제는 확실히 좀 어렵다. 처음에는 나무의 깊이가 시퀀스에서 가장 큰 하위 시퀀스를 찾을 수 있다고 생각했다. 이렇게 깊이 우선 검색을 하면 결과를 수조에 존재하고 수조에 대해 가장 큰 하위 시퀀스와 연산(노드 값을 고려하면 마이너스가 있을 수 있음)을 할 수 있지만 문제의 요구는 그렇지 않다.
제목 요구는 나무에서 연결된 통로를 찾아야 하는데 그 값이 가장 크다.
나무의 어떤 노드에 대해 말하자면 두 가지를 고려해야 한다. 하나는 이 노드에 기록될 때 권치가 얼마인지(그리고 실시간으로 최대치를 갱신하는 것), 2는 이 노드를 통과하는 경로가 왼쪽 아이에서 왔는지 오른쪽 아이에서 왔는지 기록하는 것이다. 이 두 가지 일은 반드시 각각 계산해야 한다. 최대치는 왼쪽 아이를 포함해야 하지만 경로는 왼쪽 아이나 오른쪽 아이 중 하나일 뿐이다.
코드
class Solution {
int dfs(TreeNode* root,int &maxSum)
{
if (root == NULL)
return 0;
int left = dfs(root->left,maxSum);
int right = dfs(root->right,maxSum);
int rootval = root->val + max(0, left) + max(0,right);
if (maxSum < rootval)
maxSum = rootval;
// return rootval;
return root->val + max(max(left,right),0);
}
public:
int maxPathSum(TreeNode* root) {
int maxSum = root->val;
dfs(root,maxSum);
return maxSum;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
