LeetCode113. 경로 총 II
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표 및
sum = 22 , 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
반환:
[
[5,4,11,2],
[5,8,4,5]
]제목 분석: dfs를 사용하여 잎 노드까지 순서대로 훑어보십시오. 만약에sum가 저장된 경로가 있다면.본 문제의 관건은 언제 거슬러 올라가느냐에 있다. 하나는 잎 노드를 방문할 때 거슬러 올라가야 한다는 것이다.또 하나는 한 노드의 좌우 노드를 방문한 후에도 거슬러 올라가야 한다는 것이다.
코드 표시:
class Solution {
public:
vector> pathSum(TreeNode* root, int sum) {
vector> vec;
vector temp;
dfs(root,sum,temp,vec);
return vec;
}
void dfs(TreeNode* root,int sum,vector& temp,vector>& vec){
if(root==NULL)
return;
sum -= root->val;
temp.push_back(root->val);
if(root->left==NULL && root->right==NULL){
if(sum == 0)
vec.push_back(temp);
temp.pop_back();
return;
}
dfs(root->left,sum,temp,vec);
dfs(root->right,sum,temp,vec);
temp.pop_back();
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
