二叉树非递归方式遍历

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 /**
 6  * Definition of TreeNode:
 7  * class TreeNode {
 8  * public:
 9  *     int val;
10  *     TreeNode *left, *right;
11  *     TreeNode(int val) {
12  *         this->val = val;
13  *         this->left = this->right = NULL;
14  *     }
15  * }
16  */
17 
18 
19 class TreeNode {
20 public:
21     int val;
22     TreeNode *left, *right;
23     TreeNode(int val) {
24         this->val = val;
25         this->left = this->right = NULL;
26     }
27 };
28 
29 class Solution {
30 public:
31     /**
32      * @param root: The root of binary tree.
33      * @return: Preorder in vector which contains node values.
34      */
35     struct record{
36         TreeNode* tn;
37         int state;
38         record(TreeNode* tn, int state):tn(tn),state(state){}
39     };
40     vector<int> preorderTraversal(TreeNode *root) {
41         // write your code here
42         vector<int> ans;
43         TreeNode* cur = root;
44         stack<record> s;
45         int state = 0;
46         while(1){
47             if(cur == NULL || (cur && state == 2)){
48                 if(cur == root) break;
49                 record tmp = s.top();
50                 cur = tmp.tn;
51                 state = tmp.state;
52                 s.pop();
53             } else if(state == 0){
54                 ans.push_back(cur->val);
55                 s.push(record(cur, 1));
56                 cur = cur -> left;
57             } else if(state == 1){
58                 s.push(record(cur, 2));
59                 cur = cur -> right;
60                 state = 0;
61             }
62         }
63         return ans;
64     }
65 };
66 
67 int main(){
68 
69 }