面试金典--4.4

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 #include <cmath>
11 #include <string>
12 #include <stdexcept>
13 #include <stack>
14 using namespace std;
15 
16 typedef struct treeNode
17 {
18     struct treeNode *left;
19     struct treeNode *right;
20     int val;
21     treeNode(int pval):left(NULL),right(NULL),val(pval)
22     {
23 
24     }
25 }Node;
26 
27 list<list<Node*> > ans;
28 list<Node*> cur;
29 list<Node*> parent;
30 void fun(Node *root)
31 {
32     if(root != NULL)
33     {
34         //cur = new list<Node*>();
35         cur.push_back(root);
36         while(cur.size() > 0)
37         {
38             ans.push_back(cur);
39             parent = cur;
40             //cur = new list
41             cur.clear();
42             Node* tmp;
43             list<Node *>::iterator it = parent.begin();
44             for( ; it != parent.end() ; ++it)
45             {
46                 tmp = *it;
47                 cout<<tmp->val<<endl;
48                 if(tmp->left != NULL)
49                     cur.push_back(tmp->left);
50                 if(tmp-> right != NULL)
51                     cur.push_back(tmp->right);
52             }
53         }
54     }
55     return;
56 }
57 
58 int main()
59 {
60     Node tmp(1);
61     Node *root = &tmp;
62     Node tmp2(2);
63     root->left = &tmp2;
64 
65     fun(root);
66     list<list<Node *> >::iterator it = ans.begin();
67     for( ; it != ans.end() ; ++it)
68     {
69         list<Node*> tmplis = *it;
70         list<Node *>::iterator it1 = tmplis.begin();
71         for( ; it1 != tmplis.end() ; ++it1)
72         {
73             Node * tmp3 = *it1;
74             cout<<tmp3->val<<endl;
75         }
76     }
77     return 0;
78 }