二叉樹(shù)的前序、中序容握、后序遍歷用遞歸實(shí)現(xiàn)較為簡(jiǎn)單宣脉。然而，利用遞歸實(shí)現(xiàn)則有一些挑戰(zhàn)√奘希現(xiàn)將幾種常見(jiàn)的實(shí)現(xiàn)方式做簡(jiǎn)單介紹：

二叉樹(shù)節(jié)點(diǎn)定義如下：

struct ListNode {
     int val;
      ListNode *left, *right;
     ListNode(int x) : val(x), left(NULL), right(NULL) {}
};

一塑猖、前序遍歷

前序遍歷的順序?yàn)椋褐校筇铬耍已蚬丁Ｖ辽儆袃煞N方案：

//方案一：先后將右子樹(shù)和左子放入棧中，利用棧后入先出的原理遍歷感憾。
 vector<int> preorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->right) st.push(p->right);
         if(p->left) st.push(p->left);
     }
     return res;
 }

//方案二：循環(huán)左子數(shù)蜡励，將右子樹(shù)放入棧中。左子樹(shù)為空時(shí)阻桅，依次彈棧凉倚，從最下層開(kāi)始訪問(wèn)右子樹(shù)。
 vector<int> preorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         while(p->left){
             res.push_back(p->left->val);
             if(p->right) st.push(p->right);
             p = p->left;
         }
         if(p->right) st.push(p->right);
     }
     return res;
 }

二嫂沉、中序遍歷

中序遍歷的順序?yàn)椋鹤蠡校姨苏隆Ｆ浣?jīng)典思路為：當(dāng)前節(jié)點(diǎn)有左子節(jié)點(diǎn)時(shí)杏糙，將當(dāng)前節(jié)點(diǎn)壓棧，并將左子節(jié)點(diǎn)作為當(dāng)前處理蚓土；當(dāng)前節(jié)點(diǎn)無(wú)左子節(jié)點(diǎn)時(shí)宏侍，表示左子樹(shù)都已遍歷完成，此時(shí)訪問(wèn)當(dāng)前節(jié)點(diǎn)北戏，并將右子節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)负芋。

 vector<int> inorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     TreeNode* p = root;
     while(p || !st.empty()){
         if(p){
             st.push(p);
             p = p->left;
         }
         else{
             p = st.top();
             res.push_back(p->val);
             st.pop();
             p = p->right;
         }
     }
     return res;
 }

三、后續(xù)遍歷

后序遍歷的順序?yàn)椋鹤笫扔揖啥辏小Ｒ韵陆o出兩種方案：

//方案一：當(dāng)前節(jié)點(diǎn)被讀取的條件為：無(wú)左右孩子蠕嫁，或者上一次讀取的為其左右孩子锨天。
//否則按照先右后左的方式對(duì)子節(jié)點(diǎn)壓棧。

 vector<int> postorderTraversal(TreeNode *root){
     vector<int> res;
     if(!root)  
         return res;
     stack<TreeNode *> st;
     TreeNode * pre = nullptr;
     st.push(root);
     while(!st.empty()){
         TreeNode * p = st.top();
         if( (!p->left && !p->right) ||
             (pre && (pre == p->left || pre == p->right)) ){
             res.push_back(p->val);
             st.pop();
             pre = p;
         }
         else{
             if(p->right) st.push(p->right);
             if(p->left) st.push(p->left);
         }
     }
     return res;        
 }

//方案二：后序遍歷有一種巧妙的方式：前序遍歷根節(jié)點(diǎn)剃毒，先后將左右子節(jié)點(diǎn)壓棧病袄。
//這樣的遍歷順序?yàn)椋褐新Ц常遥笠娌Ｗ詈髍everse結(jié)果脑奠，則遍歷結(jié)果變?yōu)椋鹤螅曳牛小?
 vector<int> postorderTraversal(TreeNode *root){
     vector<int> res;
     if(!root)  
         return res;
     stack<TreeNode *> st;
     st.push(root);
     while(!st.empty()){
         TreeNode * p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->left) st.push(p->left);
         if(p->right) st.push(p->right);
     }
     reverse(res.begin(), res.end());
     return res;        
 }