1 #include <stdio.h>  2 #include <iostream>  3 #include <set>  4 #include <unordered_set>  5 #include <map>  6 #include <queue>  7 #include <vector>  8 #include <string>  9 #include <stack> 10  11 using std::cout; 12 using std::endl; 13 using std::set; 14 using std::map; 15 using std::queue; 16 using std::vector; 17 using std::string; 18 using std::unordered_set; 19 using std::stack; 20 using std::begin; 21 using std::end; 22  23 class TreeNode 24 { 25 public: 26     TreeNode(int v):value(v), left(NULL), right(NULL) 27     { 28     } 29 public: 30     int value; 31     TreeNode *left; 32     TreeNode *right; 33 }; 34  35 TreeNode *postorder(TreeNode *root) 36 { 37     if (root == NULL) 38     { 39         return NULL; 40     } 41     TreeNode *right = postorder(root->left); 42     TreeNode *left = postorder(root->right); 43     TreeNode *temp = new TreeNode(root->value); 44     temp->left = left; 45     temp->right = right; 46     return temp; 47 } 48  49 TreeNode *postorderNR(TreeNode *root) 50 { 51     if (root == NULL) 52     { 53         return NULL; 54     } 55     stack<TreeNode *> sk; 56     stack<TreeNode *> sk2; 57     set<TreeNode *> s; 58     sk.push(root); 59     TreeNode *p; 60     while (sk.size() != 0) 61     { 62         p = sk.top(); 63         sk.pop(); 64         if (p->left != NULL && s.count(p->left) == 0) 65         { 66             sk.push(p); 67             sk.push(p->left); 68         } 69         else if (p->right != NULL && s.count(p->right) == 0) 70         { 71             sk.push(p); 72             sk.push(p->right); 73         } 74         else 75         { 76             cout << p->value  << ", "; 77             s.insert(p); 78             //////////////////////// 79             TreeNode *r = new TreeNode(p->value); 80             if (p->left == NULL && p->right == NULL) 81             { 82                 r->left = r->right = NULL; 83  84             } 85             else if (p->left == NULL && p->right != NULL) 86             { 87                 r->left = sk2.top(); 88                 sk2.pop(); 89                 r->right = NULL; 90             } 91             else if (p->left != NULL && p->right == NULL) 92             { 93                 r->left = NULL; 94                 r->right = sk2.top(); 95                 sk2.pop(); 96             } 97             else 98             { 99                 r->left = sk2.top();100                 sk2.pop();101                 r->right = sk2.top();102                 sk2.pop();103             }104             sk2.push(r);105         }106     }107     return sk2.top();108 }109 int main(int argc, char **argv)110 {111     TreeNode *root;112     TreeNode n1(1);113     TreeNode n2(2);114     TreeNode n3(3);115     TreeNode n4(4);116     TreeNode n5(5);117     TreeNode n6(6);118     TreeNode n7(7);119     TreeNode n8(8);120     n1.left = &n2;121     n1.right = &n3;122     n2.left = &n4;123     n2.right = &n5;124     n3.left = &n6;125     n3.right = &n7;126     n4.left = &n8;127     root = &n1;128     TreeNode *result = postorderNR(root);129 130     getchar();131     return 0;132 }