1、前序遍历非递归实现
1 class Solution {
2 public:
3 /*
4 * @param root: A Tree
5 * @return: Preorder in ArrayList which contains node values.
6 */
7 vector<int> preorderTraversal(TreeNode * root) {
8 vector<int> res;
9 if(root==NULL)return res;
10 std::stack<TreeNode *> sta;
11 sta.push(root);
12 while(sta.size())
13 {
14 TreeNode *p=sta.top();
15 sta.pop();
16 res.push_back(p->val);
17 if(p->right)sta.push(p->right);
18 if(p->left)sta.push(p->left);
19 }
20 return res;
21 }
22 };
2、中序遍历非递归实现
1 class Solution {
2 public:
3 /*
4 * @param root: A Tree
5 * @return: Inorder in ArrayList which contains node values.
6 */
7 vector<int> inorderTraversal(TreeNode * root) {
8 vector<int> res;
9 if(root==NULL)return res;
10 std::stack<TreeNode *> sta;
11 TreeNode *p=root;
12 while(p || sta.size())
13 {
14 if(p){
15 sta.push(p);
16 p=p->left;
17 }else{
18 p=sta.top();
19 sta.pop();
20 res.push_back(p->val);
21 p=p->right;
22 }
23 }
24 return res;
25 }
26 };
3、后序遍历非递归实现
1 class Solution {
2 public:
3 /*
4 * @param root: A Tree
5 * @return: Postorder in ArrayList which contains node values.
6 */
7 vector<int> postorderTraversal(TreeNode * root) {
8 vector<int> res;
9 if(root==NULL)return res;
10 std::stack<TreeNode *> sta;
11 std::stack<int> help;//增加一个辅助栈
12 sta.push(root);
13 while(sta.size())
14 {
15 TreeNode *p=sta.top();
16 sta.pop();
17 help.push(p->val);//先放入辅助栈
18 if(p->left)sta.push(p->left);
19 if(p->right)sta.push(p->right);
20 }
21 while(help.size())//再从辅助栈内倒出
22 {
23 int tmp=help.top();
24 help.pop();
25 res.push_back(tmp);
26 }
27 return res;
28 }
29 };