二叉樹是一種重要的數據結構，對二叉樹的遍歷也很重要。這里簡單介紹三種二叉樹中序遍歷的方法。二叉樹的中序遍歷就是首先遍歷左子樹，然后訪問當前節點，最后遍歷右子樹。對于下面的二叉樹，中序遍歷結果如下：
結果：[5,10,6,15,2]
直觀來看，二叉樹的中序遍歷就是將節點投影到一條水平的坐標上。如圖：
1、遞歸法
這是思路最簡單的方法，容易想到并且容易實現。遞歸的終止條件是當前節點是否為空。首先遞歸調用遍歷左子樹，然后訪問當前節點，最后遞歸調用右子樹。代碼如下：
//recursive
class Solution1 {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ret;if(root==NULL)return ret;inorderHelper(ret,root);return ret;}
private:void inorderHelper(vector<int>& ret,TreeNode* root){if(root==NULL)return;inorderHelper(ret,root->left);ret.push_back(root->val);inorderHelper(ret,root->right);}
};2、迭代法
在迭代方法中，從根節點開始找二叉樹的最左節點，將走過的節點保存在一個棧中，找到最左節點后訪問，對于每個節點來說，它都是以自己為根的子樹的根節點，訪問完之后就可以轉到右兒子上了。代碼如下：
//iterate,using a stack
class Solution2 {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ret;if(root==NULL)return ret;TreeNode *curr=root;stack<TreeNode*> st;while(!st.empty()||curr!=NULL){while(curr!=NULL){st.push(curr);curr=curr->left;}curr=st.top();st.pop();ret.push_back(curr->val);curr=curr->right;}return ret;}
};3、Morris法
這種方法是Morris發明的，看完之后感覺精妙無比。這種方法不使用遞歸，不使用棧，O(1)的空間復雜度完成二叉樹的遍歷。這種方法的基本思路就是將所有右兒子為NULL的節點的右兒子指向后繼節點（對于右兒子不為空的節點，右兒子就是接下來要訪問的節點）。這樣，對于任意一個節點，當訪問完它后，它的右兒子已經指向了下一個該訪問的節點。對于最右節點，不需要進行這樣的操作。注意，這樣的操作是在遍歷的時候完成的，完成訪問節點后會把樹還原。整個循環的判斷條件為當前節點是否為空。例如上面的二叉樹，遍歷過程如下（根據當前節點c的位置）：
（1）當前節點為10，因為左兒子非空，不能訪問，找到c的左子樹的最右節點p：
結果：[]
（2）找節點c的左子樹的最右節點有兩種終止條件，一種右兒子為空，一種右兒子指向當前節點。下面是右兒子為空的情況，這種情況先要構造，將節點p的右兒子指向后繼節點c，然后c下移：
結果：[]
（3）當前節點c的左兒子為空，進行訪問。訪問后將c指向右兒子（即后繼節點）：
結果：[5]
（4）繼續尋找左子樹的最右節點，這次的終止條件是最右節點為當前節點。這說明當前節點的左子樹遍歷完畢，訪問當前節點后，還原二叉樹，將當前節點指向后繼節點：
結果：[5,10]
（5）重復上述過程，直到c指向整棵二叉樹的最右節點：
左兒子為空，進行訪問，c轉到右兒子。右兒子為空，不滿足判斷條件，循環結束，遍歷完成。結果如下：
[5,10,6,15,2]
這就是Morris方法，時間復雜度為O(n)，空間復雜度是O(1)。代碼如下：
//Morris traversal,without a stack
class Solution3 {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ret;if(root==NULL)return ret;TreeNode *curr=root;TreeNode *pre;while(curr){if(curr->left==NULL){ret.push_back(curr->val);curr=curr->right;}else{pre=curr->left;while(pre->right&&pre->right!=curr)pre=pre->right;if(pre->right==NULL){pre->right=curr;curr=curr->left;}else{ret.push_back(curr->val);pre->right=NULL;curr=curr->right;}}}return ret;}
};
)
)
)
