面试：C++二叉树遍历（递归/非递归）

  1 #include <vector>
  2 #include <stack>
  3 #include <queue>
  4 using namespace std;
  5 
  6 
  7 struct TreeNode{
  8     int val;
  9     TreeNode* left;
 10     TreeNode* right;
 11     TreeNode(int x):val(x),left(nullptr),right(nullptr){};
 12 };
 13 
 14 void preOrder(TreeNode* root,vector<int>& res){
 15     if(root == nullptr) return;
 16     res.push_back(root->val);
 17     preOrder(root->left,res);
 18     preOrder(root->right,res);
 19 }
 20 
 21 void inOrder(TreeNode* root,vector<int>& res){
 22     if(root == nullptr) return;
 23     inOrder(root->left,res);
 24     res.push_back(root->val);
 25     inOrder(root->right,res);
 26 }
 27 
 28 void postOrder(TreeNode* root,vector<int>& res){
 29     if(root == nullptr) return;
 30     postOrder(root->left,res);
 31     postOrder(root->right,res);
 32     res.push_back(root->val);
 33 }
 34 
 35 
 36 vector<int> preOrder(TreeNode* root){
 37     vector<int> res;
 38     if(root == nullptr) return res;
 39 
 40     stack<TreeNode*> st;
 41     TreeNode* cur = root;
 42     while(cur || !st.empty()){
 43         while(cur){
 44             res.push_back(cur->val);
 45             st.push(cur);
 46             cur = cur->left;
 47         }
 48         if(!st.empty()){
 49             cur = st.top();
 50             st.pop();
 51             cur = cur->right;
 52         }
 53     }
 54     return res;
 55 }
 56 
 57 
 58 vector<int> inOrder(TreeNode* root){
 59     vector<int> res;
 60     if(root==nullptr) return res;
 61 
 62     stack<TreeNode*> st;
 63     TreeNode* cur = root;
 64     while(cur || !st.empty()){
 65         while(cur){
 66             st.push(cur);
 67             cur = cur->left;
 68         }
 69         if(!st.empty()){
 70             cur = st.top();
 71             st.pop();
 72             res.push_back(cur->val);
 73             cur = cur->right;
 74         }
 75     }
 76     return res;
 77 }
 78 
 79 
 80 vector<int> postOrder(TreeNode* root){
 81     vector<int> res;
 82     if(root == nullptr) return res;
 83 
 84     stack<TreeNode*> st;
 85     TreeNode* cur = root;
 86     while(cur){
 87         st.push(cur);
 88         cur = cur->left;
 89     }
 90 
 91     TreeNode* lastVisited = nullptr;
 92     while(!st.empty()){
 93         cur = st.top();
 94         st.pop();
 95         if(cur->right == nullptr || cur->right == lastVisited){
 96             res.push_back(cur->val);
 97             lastVisited = cur;
 98         }else{
 99             st.push(cur);
100             cur = cur->right;
101             while(cur){
102                 st.push(cur);
103                 cur = cur->left;
104             }
105         }
106     }
107     return res;
108 }
109 
110 vector<int> levelOrder(TreeNode* root){
111     vector<int> res;
112     if(root == nullptr) return res;
113 
114     queue<TreeNode*> q;
115     q.push(root);
116     while(!q.empty()){
117         size_t n = q.size();
118         for(size_t i=0;i<n;i++){
119             TreeNode* cur = q.back();
120             q.pop();
121             res.push_back(cur->val);
122             if(cur->left) q.push(cur->left);
123             if(cur->right) q.push(cur->right);
124         }
125     }
126     return res;
127 }