LeetCode(113)Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 /\ 4 8 / /\ 11 13 4 / \ /\ 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ]
분석은 다음과 같습니다.
이전 문제와 비교적 비슷해서 이 문제도 귀속을 이용하여 검색할 수 있다.다른 것은 이 문제는 모든 정확한 경로를 보존해야 한다는 것이다. 만약에 층차적으로 훑어보면 저장해야 할 것이 너무 많다. 만약에 귀속을 사용하고 현재의 해를 찾은 후에 거슬러 올라가면 비교적 쉽다.나는 아직 거슬러 올라가는 것에 익숙하지 않아서 인터넷의 몇 가지 답안을 참고하여 거슬러 올라가는 코드를 썼다.
내 코드:
class Solution {
public:
vector<vector<int> > large_vec;
vector<int> small_vec;
void pathSum_(TreeNode *root, int sum) {
if(root!=NULL&&root->left==NULL&&root->right==NULL&&sum==root->val){
small_vec.push_back(root->val);
large_vec.push_back(small_vec);
return;
}
small_vec.push_back(root->val);
if(root!=NULL&&root->left!=NULL){
pathSum_(root->left, sum-root->val);
small_vec.pop_back();
}
if(root!=NULL&&root->right!=NULL){
pathSum_(root->right,sum-root->val);
small_vec.pop_back();
}
}
vector<vector<int> > pathSum(TreeNode *root, int sum) {
large_vec.clear();
small_vec.clear();
if(root==NULL)
return large_vec;
pathSum_(root, sum);
return large_vec;
}
};
update: 2014- 11- 26
우선, DFS에 대한 회고와 이해가 깊지 않아서 다시 썼는데 위의 방법과 기본적으로 같다.이 예로 거슬러 올라가면 매우 그리워진다.sum = 3, 가능한 경로는 4개입니다.
1
1 1
1 1 1 1
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
void myPathSum(TreeNode *root, int sum, vector<int>& path_result, vector<vector<int> >& all_result) {
if (root->left == NULL && root->right == NULL && sum == root->val) {
path_result.push_back(root->val);
all_result.push_back(path_result);
return;
}else {
path_result.push_back(root->val);
if (root->left != NULL) {
myPathSum(root->left, sum - root->val, path_result, all_result);
path_result.pop_back(); //
}
if (root->right != NULL) {
myPathSum(root->right, sum - root->val, path_result, all_result);
path_result.pop_back(); //
}
}
}
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
vector<int> path_result;
vector<vector<int> > all_result;
if (root != NULL)
myPathSum(root, sum, path_result, all_result);
return all_result;
}
};그 다음으로 코드가 낫기 위해서는 공간을 희생할 수 있다.위의 코드에서 임의의 후보를 나타내는 단일 경로의 변수인vector
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// ， 。
class Solution {
private:
void myPathSum(TreeNode *root, int sum, vector<int> path_result, vector<vector<int> >& all_result) {
if (root->left == NULL && root->right == NULL && sum == root->val) {
path_result.push_back(root->val);
all_result.push_back(path_result);
return;
}else {
path_result.push_back(root->val);
if (root->left != NULL) {
myPathSum(root->left, sum - root->val, path_result, all_result);
}
if (root->right != NULL) {
myPathSum(root->right, sum - root->val, path_result, all_result);
}
}
}
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
vector<int> path_result;
vector<vector<int> > all_result;
if (root != NULL)
myPathSum(root, sum, path_result, all_result);
return all_result;
}
};거슬러 올라가지 않은 코드, 112ms.
참고 자료:
(1) http://yucoding.blogspot.com/2013/04/leetcode-question-67-path-sum-ii.html(2) 송아지 왼쪽 귀 쥐의source code
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
