코드 문제 (28) - 전체 경로 시리즈, 두 갈래 트리의 모든 경로
1、112.경로 합계
두 갈래 나무와 목표를 정하고 이 나무에 뿌리 노드가 잎 노드까지의 경로가 있는지 판단한다. 이 경로에 있는 모든 노드 값은 목표와 같다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표 및
sum = 22를 지정합니다. 5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1목표와 22의 뿌리 노드가 잎 노드로 가는 경로
true가 존재하기 때문에 되돌아오기5->4->11->2.이 두 갈래 트리의 경로는 깊이 우선 알고리즘 DFS의 사상으로 모든 완전한 경로를 옮겨야 한다. 즉, 귀속을 이용하여 하위 노드의 좌우 하위 노드를 끊임없이 찾고 귀속 함수를 호출하는 매개 변수는 현재 노드와sum값뿐이다.우선, 입력한 것이 빈 노드라면false를 직접 되돌려주고, 입력한 것이 루트 노드만 있다면, 현재 루트 노드의 값과 매개 변수sum값이 같은지, 같은지,true를 되돌려주고, 그렇지 않으면false를 비교합니다.이 조건도 귀속의 중지 조건이다.다음에 우리는 귀속을 시작할 것이다. 함수의 반환 값은 Ture/False이기 때문에 우리는 동시에 두 방향으로 함께 귀속할 수 있다. 중간에 사용하거나 | | 연결을 할 수 있다. 하나만 True라면 전체 결과는 True이다.좌우 노드에 귀속할 때, 이때의sum값은 원래sum값에서 현재 노드의 값을 빼야 한다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root == nullptr || sum<=0)
return false;
if(root->left==nullptr && root->right==nullptr && root->val == sum)
return true;
return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right, sum-root->val);
}
};2、113.경로 총 II
두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표 및
sum = 22를 지정합니다. 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
반환:
[
[5,4,11,2],
[5,8,4,5]
]DFS를 깊이 있게 우선 검색해야 합니다. 데이터 구조가 상대적으로 복잡할 뿐, 2차원vector를 사용해야 하며, DFS가 새 노드를 검색할 때마다 이 노드를 저장해야 합니다.그리고 경로를 찾을 때마다 1차원vector로 저장된 경로를 최종 결과인 2차원vector에 저장합니다.그리고 DFS가 하위 노드를 검색할 때마다 경로와 경로가 아닌 것을 발견하면 이전 결점으로 돌아갈 때 이 노드를 1차원vector에서 제거해야 합니다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vectorint>> pathSum(TreeNode* root, int sum) {
vectorint>> res;
if(root == nullptr)
return res;
vector<int> temp;
findPath(root,sum,temp,res);
return res;
}
void findPath(TreeNode* root,int sum,vector<int> &temp,vectorint>> &res)
{
if(root == nullptr)
return;
temp.push_back(root->val);
sum -= root->val;
if(root->left==nullptr && root->right==nullptr && sum==0)
{
res.push_back(temp);
}
else
{
findPath(root->left,sum,temp,res);
findPath(root->right,sum,temp,res);
}
temp.pop_back();
}
}; 3、 437.경로 총 III
두 갈래 나무를 정해 주면 결점마다 정수치가 저장되어 있다.
경로와 주어진 수치와 같은 경로의 총수를 찾아라.
경로는 루트 노드에서 시작할 필요도 없고 잎 노드에서 끝날 필요도 없지만 경로 방향은 아래쪽이어야 합니다 (부모 노드에서 하위 노드까지만).
두 갈래 나무는 1000개의 노드를 초과하지 않고 노드의 수치 범위는 [-1000000, 10000000]의 정수이다.
예:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
3。 8 :
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11이 문제는 우리가 두 갈래 나무의 경로의 합을 구하는 데 주어진 값과 같다. 이것은 이 경로가 뿌리 노드에서 시작할 필요가 없고 중간의 임의의 단락이 될 수 있으며 두 갈래 나무의 노드 값도 정과 음이 있다는 것을 설명한다.그러면 우리는 귀속으로 할 수 있다. 이는 두 갈래 나무를 먼저 훑어보는 것과 같다. 모든 노드에 대해 루트 노드에서 현재 노드까지의 경로를 기록하고 변수curSum으로 경로 노드의 총계를 기록한다. 그리고 우리는curSum과sum이 같은지 아닌지를 본다. 같으면 결과res가 1을 추가한다. 기다리지 않으면 우리는 하위 경로와 주제가 충족되는지 계속 살펴보자. 방법은 매번 노드를 제거하는 것이다.경로와 주어진 값이 맞는지 확인하려면 마지막에 노드를 남겨야 합니다. 모두 제거할 수 없습니다. 만약 모두 제거한다면 경로의 합은 0이고, 만약 주어진 값이 마침 0이라면 문제가 있기 때문입니다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
int res=0;
if(root==nullptr)
return res;
vector temp;
pathAll(root,sum,0,temp,res);
return res;
}
void pathAll(TreeNode* root, int sum, int cursum, vector &temp, int &res)
{
if(root==nullptr)
return;
temp.push_back(root);
cursum += root->val;
if(cursum==sum)
res++;
int t = cursum;
for(int i=0;i1;++i) // ， sum=0
{
t -= temp[i]->val;
if(t==sum)
res++;
}
pathAll(root->left, sum, cursum,temp,res);
pathAll(root->right, sum, cursum, temp, res);
temp.pop_back();
}
}; 4、257.두 갈래 나무의 모든 경로
두 갈래 나무를 정해서 뿌리 노드에서 잎 노드까지의 모든 경로를 되돌려줍니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예:
:
1
/ \
2 3
\
5
: ["1->2->5", "1->3"]
: : 1->2->5, 1->3이 문제는 우리에게 두 갈래 나무를 하나 주었다. 우리는 모든 뿌리에서 잎 노드로 돌아가는 경로를 되돌려 주었다. 이전의 Path Sum II와 유사하다. 그보다 조금 간단하다. 경로를 계산할 필요가 없고 모든 경로를 뇌가 없으면 된다. 그러면 사고방식은 귀속으로 풀 수 있다. 블로거는 이전에 나무놀이의 문제는 십중팔구는 귀속이고 귀속의 핵심은 끊임없이 DFS에서 잎결점으로 돌아가는 것이라고 강조했다.그리고 거슬러 올라가.귀속 함수에서 우리가 엽결점을 만났을 때 좌우자 결점이 없었다. 그러면 이때 완전한 경로가 형성되었다. 우리는 현재의 엽결점을 추가한 후에 결과res에 저장한 다음에 거슬러 올라간다.이 결과res는reference가 필요하고out는 인용할 필요가 없습니다. 그렇지 않으면 거슬러 올라가서 새로 추가된 결점을 삭제하는 것이 번거롭습니다.공결점을 판단하는 절차를 줄이기 위해 우리는 귀속 함수를 호출하기 전에 모두 비공을 검사하면 된다. 코드는 매우 간결하다. 아래를 참조한다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(root==nullptr)
return res;
string temp;
binary(root, temp, res);
return res;
}
void binary(TreeNode* root, string temp, vector<string> &res )
{
if(!root->left && !root->right)
res.push_back(temp+to_string(root->val));
if(root->left)
{
binary(root->left, temp+to_string(root->val)+"->",res);
}
if(root->right)
{
binary(root->right, temp+to_string(root->val)+"->",res);
}
}
};다음으로 전송:https://www.cnblogs.com/eilearn/p/9394203.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
