알고리즘 문제 25 두 갈래 나무의 뒷순서가 변형된 두 갈래 나무와 어떤 값의 경로를 반복한다

7559 단어
제목
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.나무의 뿌리 결점에서 시작하여 잎 결점이 지나가는 결점까지 내려가서 하나의 경로를 형성한다.
분석
우리는 잠시 나무의 뿌리 노드에서부터 잎 노드가 지나가는 노드가 형성하는 경로를 수직 경로라고 부른다.검색 과정을 자세히 시뮬레이션하여 하나의 잎 노드를 찾았을 때, 부모 노드의 오른쪽 아이 (이 잎 노드는 왼쪽 아이) 를 방문하거나, 상부 노드로 되돌아간다.경로 인쇄가 필요하기 때문에 왼쪽 트리에 접근한 후에도 부모 노드는 캐시를 유지하고 오른쪽 트리를 찾고 조건에 맞는 경로를 인쇄할 때까지 기다려야 한다.오른쪽 하위 트리에 접근한 후에 다시 이 부모 노드를 방문하면 부모 노드의 좌우 하위 트리가 조회되어 상위 부모 노드로 돌아갑니다.분명히 이 과정에서 한 부모 노드는 세 번 (처음 훑어보고, 왼쪽 아이는 돌아오고, 오른쪽 아이는 돌아오고) 방문하기 때문에 부모 노드만 저장하는 것은 부족하고, 도대체 몇 번째 방문인지 기록해야 한다.이것이 바로 뒷차례가 두루 다니는구나!그러므로 앞뒤가 두루 흐르는 방법으로 이 문제를 풀다
코드
 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 }

 

좋은 웹페이지 즐겨찾기