面试题11：二叉树的非递归前、中、后、层级遍历

 1 #include <vector>
 2 #include <stack>
 3 using std::vector;
 4 
 5 struct TreeNode {
 6     int val;
 7     TreeNode* left;
 8     TreeNode* right;
 9     TreeNode(int x) :
10             val(x), left(nullptr), right(nullptr) {
11     }
12 };
13 
14 vector<int> preOrder(TreeNode* root) {
15     vector<int> res;
16     if (root == nullptr)
17         return res;
18 
19     std::stack<TreeNode*> s;
20     TreeNode* p = root;
21     while (p || !s.empty()) {
22         while (p) {
23             res.push_back(p->val);
24             s.push(p);
25             p = p->left;
26         }
27 
28         if (!s.empty()) {
29             p = s.top();
30             s.pop();
31             p = p->right;
32         }
33     }
34     return res;
35 }
36 
37 vector<int> inOrder(TreeNode* root) {
38     vector<int> res;
39     if (root == nullptr)
40         return res;
41     TreeNode* p = root;
42     std::stack<TreeNode*> s;
43 
44     while (p || !s.empty()) {
45 
46         while (p) {
47             s.push(p);
48             p = p->left;
49         }
50 
51         if (!s.empty()) {
52             p = s.top();
53             s.pop();
54             res.push_back(p->val);
55             p = p->right;
56         }
57     }
58     return res;
59 }
60 
61 vector<int> postorderTraversal(TreeNode* root) {
62     vector<int> res;
63     if (root == nullptr)
64         return res;
65 
66     std::stack<TreeNode*> s;
67     TreeNode* cur = root;
68     TreeNode* pre = nullptr;
69 
70     while (cur) {
71         s.push(cur);
72         cur = cur->left;
73     }
74 
75     while (!s.empty()) {
76         cur = s.top();
77         s.pop();
78         if (cur->right == nullptr || cur->right == pre) {
79             res.push_back(cur->val);
80             pre = cur;
81         } else {
82             s.push(cur);
83             cur = cur->right;
84             while (cur) {
85                 s.push(cur);
86                 cur = cur->left;
87             }
88         }
89     }
90     return res;
91 }