두 갈래 나무 한 그루를 정하고, 매 결점마다 값을 포함한다.다음 조건을 충족하는 모든 경로를 인쇄합니다. 경로에 있는 끝점의 값을 합치면 주어진 값과 같습니다.참고: 이러한 경로는 루트 끝점에서 시작할 필요가 없습니다.

두 갈래 나무 한 그루를 정하고, 매 결점마다 값을 포함한다.다음 조건을 충족하는 모든 경로를 인쇄합니다. 경로에 있는 끝점의 값을 합치면 주어진 값과 같습니다.참고: 이러한 경로는 루트 끝점에서 시작할 필요가 없습니다.
 

해답

 
방안1: 결점에 아버지의 결점을 가리키는 지침이 포함되어 있다면, 이 두 갈래 나무를 두루 훑어본 다음, 각 결점부터 아버지의 결점이 비어 있을 때까지 아버지의 결점 값을 끊임없이 누적할 수 있다. (이것은 유일성을 가진다. 왜냐하면 모든 결점에는 아버지의 결점이 하나밖에 없기 때문이다. 또한 이 유일성 때문에 별도의 공간을 열어 경로를 저장하지 않을 수 있다. 만약에 주어진 값sum과 같다면,출력을 인쇄합니다.
코드는 다음과 같습니다.

void find_sum(Node* head, int sum){ if(head == NULL) return; Node *no = head; int tmp = 0; for(int i=1; no!=NULL; ++i){ tmp += no->key; if(tmp == sum) print(head, i); no = no->parent; } find_sum(head->lchild, sum); find_sum(head->rchild, sum); } 

출력을 인쇄할 때 현재 결점에 대한 포인터와 누적된 층수만 제공하면 된다.그리고 현재 결점부터 아버지 결점의 값(현재 결점 포함)을 누적 층수에 도달할 때까지 계속 저장한 다음 역순으로 출력하면 된다.
코드는 다음과 같습니다.

void print(Node* head, int level){ vector<int> v; for(int i=0; i<level; ++i){ v.push_back(head->key); head = head->parent; } while(!v.empty()){ cout<<v.back()<<" "; v.pop_back(); } cout<<endl; } 

방안2: 만약에 결점에 아버지의 결점을 가리키는 바늘이 포함되지 않는다면 두 갈래 나무가 위에서 아래로 경로를 찾는 과정에서 매번의 경로에 중간 결과를 저장해야 한다. 누적된 구애와 여전히 아래에서 위로, 저장된 경로에 대응하는 수조, 즉 수조의 뒤에서부터 누적된 것이다. 이렇게 하면 모든 경로를 두루 다닐 수 있다.
코드는 다음과 같습니다.

void print2(vector<int> v, int level){ for(int i=level; i<v.size(); ++i) cout<<v.at(i)<<" "; cout<<endl; } void find_sum2(Node* head, int sum, vector<int> v, int level){ if(head == NULL) return; v.push_back(head->key); int tmp = 0; for(int i=level; i>-1; --i){ tmp += v.at(i); if(tmp == sum) print2(v, i); } vector<int> v1(v), v2(v); find_sum2(head->lchild, sum, v1, level+1); find_sum2(head->rchild, sum, v2, level+1); } 

방안1과 방안2의 본질 사상은 사실 같다. 다른 것은 아버지의 결점을 가리키는 지침이 있는지의 여부일 뿐이다.만약 이 정보가 없다면, 중간 정보를 저장하기 위해 많은 추가 공간이 필요하다.
주의: 방안 1과 방안 2 코드의 level은 같은 개념을 가리키는 것이 아니라 방안 1의 level은 층수를 나타내고 최소값은 1이다.방안 2에서 level은 몇 층을 표시하고 최소값은 0입니다.
전체 코드는 다음과 같습니다.

#include <iostream> #include <vector> #include <cstring> using namespace std; const int maxn = 100; struct Node{ int key; Node *lchild, *rchild, *parent; }; Node node[maxn]; int cnt; void init(){ memset(node, '\0', sizeof(node)); cnt = 0; } void create_minimal_tree(Node* &head, Node *parent, int a[], int start, int end){ if(start <= end){ int mid = (start + end)>>1; node[cnt].key = a[mid]; node[cnt].parent = parent; head = &node[cnt++]; create_minimal_tree(head->lchild, head, a, start, mid-1); create_minimal_tree(head->rchild, head, a, mid+1, end); } } void print(Node* head, int level){ vector<int> v; for(int i=0; i<level; ++i){ v.push_back(head->key); head = head->parent; } while(!v.empty()){ cout<<v.back()<<" "; v.pop_back(); } cout<<endl; } void find_sum(Node* head, int sum){ if(head == NULL) return; Node *no = head; int tmp = 0; for(int i=1; no!=NULL; ++i){ tmp += no->key; if(tmp == sum) print(head, i); no = no->parent; } find_sum(head->lchild, sum); find_sum(head->rchild, sum); } void print2(vector<int> v, int level){ for(int i=level; i<v.size(); ++i) cout<<v.at(i)<<" "; cout<<endl; } void find_sum2(Node* head, int sum, vector<int> v, int level){ if(head == NULL) return; v.push_back(head->key); int tmp = 0; for(int i=level; i>-1; --i){ tmp += v.at(i); if(tmp == sum) print2(v, i); } vector<int> v1(v), v2(v); find_sum2(head->lchild, sum, v1, level+1); find_sum2(head->rchild, sum, v2, level+1); } int main(){ init(); int a[] = { 4, 3, 8, 5, 2, 1, 6 }; Node *head = NULL; create_minimal_tree(head, NULL, a, 0, 6); // find_sum(head, 8); vector<int> v; find_sum2(head, 8, v, 0); return 0; }