알고리즘 문제 25 두 갈래 나무의 뒷순서가 변형된 두 갈래 나무와 어떤 값의 경로를 반복한다
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.나무의 뿌리 결점에서 시작하여 잎 결점이 지나가는 결점까지 내려가서 하나의 경로를 형성한다.
분석
우리는 잠시 나무의 뿌리 노드에서부터 잎 노드가 지나가는 노드가 형성하는 경로를 수직 경로라고 부른다.검색 과정을 자세히 시뮬레이션하여 하나의 잎 노드를 찾았을 때, 부모 노드의 오른쪽 아이 (이 잎 노드는 왼쪽 아이) 를 방문하거나, 상부 노드로 되돌아간다.경로 인쇄가 필요하기 때문에 왼쪽 트리에 접근한 후에도 부모 노드는 캐시를 유지하고 오른쪽 트리를 찾고 조건에 맞는 경로를 인쇄할 때까지 기다려야 한다.오른쪽 하위 트리에 접근한 후에 다시 이 부모 노드를 방문하면 부모 노드의 좌우 하위 트리가 조회되어 상위 부모 노드로 돌아갑니다.분명히 이 과정에서 한 부모 노드는 세 번 (처음 훑어보고, 왼쪽 아이는 돌아오고, 오른쪽 아이는 돌아오고) 방문하기 때문에 부모 노드만 저장하는 것은 부족하고, 도대체 몇 번째 방문인지 기록해야 한다.이것이 바로 뒷차례가 두루 다니는구나!그러므로 앞뒤가 두루 흐르는 방법으로 이 문제를 풀다
코드
1 void PrintSumPath2(TreeNode* root,int number)
2 {
3 if (!root)
4 {
5 cout<<"the tree is empty!"<<endl;
6 return;
7 }
8
9 stack<TreeNode*> s_parents;
10 map<TreeNode*,int> map_tag;
11
12 int sum=0;
13
14 TreeNode* node=root;
15 while(node||!s_parents.empty())
16 {
17 if (map_tag.find(node)==map_tag.end())// ,
18 {
19 while (node)
20 {
21 s_parents.push(node);
22 map_tag.insert(make_pair(node,1));
23
24 sum+=node->value;
25 if (sum>number)
26 break;
27
28 node=node->pLeft;
29 }
30
31 if(sum==number&&node==NULL)// ,
32 {
33 PrintSubPath(s_parents);
34 }
35
36 node=s_parents.top();
37 //cout<<node->value<<endl;
38 sum-=node->value;
39 s_parents.pop();
40 }
41
42 if (s_parents.empty())
43 {
44 break;
45 }
46
47 node=s_parents.top();
48 if (map_tag[node]==2)// ,pop
49 {
50 //cout<<node->value<<endl;
51 sum-=node->value;
52 s_parents.pop();
53 }else // =1, ,
54 {
55 map_tag[node]+=1;
56 node=node->pRight;
57 }
58 }
59
60 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.