前序遍歷：先訪問該節(jié)點(diǎn)，然后訪問該節(jié)點(diǎn)的左子樹和右子樹；
中序遍歷：先訪問該節(jié)點(diǎn)的左子樹，然后訪問該節(jié)點(diǎn)，再訪問該節(jié)點(diǎn)的右子樹；
后序遍歷：想訪問該節(jié)點(diǎn)的左子樹和右子樹，然后訪問該節(jié)點(diǎn)。
遞歸遍歷
?
對(duì)于遞歸遍歷比較簡(jiǎn)單：
?
void preorder(TreeNode* root) {
????if (root == NULL)
????????return;
????visit(root);
????preorder(root->left);
????preorder(root->right);
}
?
void inorder(TreeNode* root) {
????if (root == NULL)
????????return;
????inorder(root->left);
????visit(root);
????inorder(root- }
?
void postorder(TreeNode* root) {
????if (root == NULL)
????????return;
????postorder(root->left);
????postorder(root->right);
????visit(root);
}
非遞歸（迭代）遍歷
?
非遞歸實(shí)現(xiàn)在遍歷根節(jié)點(diǎn)后還要回來，因此要基于棧（先進(jìn)后出）來保存節(jié)點(diǎn)。
注：二叉樹遍歷的非遞歸實(shí)現(xiàn)文章里有不同的實(shí)現(xiàn)方式，更易于理解記憶。
?
前序遍歷
?
壓入順序：右子樹->左子樹->根節(jié)點(diǎn)
使得訪問的時(shí)候的順序成為：根->左子樹->右子樹
?
????vector preorderTraversal(TreeNode* root) {
????????vector result;
????????stack s;
????????if (root == NULL)
????????????return result;
????????s.push(root);
????????while(!s.empty()) {
????????????TreeNode* p = s.top();
????????????s.pop();
????????????result.push_back(p->val);
????????????if (p->right)
????????????????s.push(p->right);
????????????if (p->left)
????????????????s.push(p->left);
????????}
????????return result;
????}
中序遍歷
?
壓入順序：右子樹->根->左子樹
只有當(dāng)左子樹已經(jīng)訪問完后，才能訪問根節(jié)點(diǎn)
?
對(duì)于任一結(jié)點(diǎn)P，
1)若其左孩子不為空，則將P入棧并將P的左孩子置為當(dāng)前的P，然后對(duì)當(dāng)前結(jié)點(diǎn)P再進(jìn)行相同的處理；
2)若其左孩子為空，則取棧頂元素并進(jìn)行出棧操作，訪問該棧頂結(jié)點(diǎn)，然后將當(dāng)前的P置為棧頂結(jié)點(diǎn)的右孩子；
3)直到P為NULL并且棧為空則遍歷結(jié)束
vector inorderTraversal(TreeNode* root) {
????????vector result;
????????stack s;
????????if (root == NULL)
????????????return result;
????????TreeNode* p = root;
????????while (!s.empty() || p != NULL) {
????????????if (p != NULL) {
????????????????// push 左子樹入棧
????????????????s.push(p);
????????????????p = p->left;
????????????} else {
????????????????// 左子樹為空時(shí)，訪問該節(jié)點(diǎn)，然后訪問右子樹
????????????????p = s.top();
????????????????result.push_back(p->val);
????????????????s.pop();
????????????????p = p->right;
????????????}
????????}
????????return result; ?
????}
后序遍歷
先壓入根，然后是右子樹，最后左子樹
要求最后訪問根節(jié)點(diǎn)，即訪問該根節(jié)點(diǎn)時(shí)必須訪問完左子樹和右子樹，我們只需要保證訪問某一節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)的右子樹已經(jīng)被訪問，否則需要將該節(jié)點(diǎn)重新壓入棧。
?
對(duì)于任一結(jié)點(diǎn)P，將其入棧，然后沿其左子樹一直往下搜索，直到搜索到?jīng)]有左孩子的結(jié)點(diǎn)，此時(shí)該結(jié)點(diǎn)出現(xiàn)在棧頂，但是此時(shí)不能將其出棧并訪問，因此其右孩子還為被訪問。所以接下來按照相同的規(guī)則對(duì)其右子樹進(jìn)行相同的處理，當(dāng)訪問完其右孩子時(shí)，該結(jié)點(diǎn)又出現(xiàn)在棧頂，此時(shí)可以將其出棧并訪問。這樣就保證了正確的訪問順序。可以看出，在這個(gè)過程中，每個(gè)結(jié)點(diǎn)都兩次出現(xiàn)在棧頂，只有在第二次出現(xiàn)在棧頂時(shí)，才能訪問它。
??vector postorderTraversal(TreeNode* root) {
????????vector result;
????????if (root == NULL)
????????????return result;
????????stack s;
????????TreeNode* p = root; ?//當(dāng)前正訪問的節(jié)點(diǎn)
????????TreeNode* q; ?//記錄剛剛訪問過的節(jié)點(diǎn)
????????do{
????????????while (p != NULL) {
????????????????s.push(p);
????????????????p = p->left;
????????????}
????????????q = NULL;
????????????while (!s.empty()) {
????????????????p = s.top();
????????????????s.pop();
????????????????if (p->right == q) { ?//當(dāng)右子樹已經(jīng)訪問過了，才可以訪問根
????????????????????result.push_back(p->val);
????????????????????q = p; ?//記錄剛剛訪問過的節(jié)點(diǎn)
????????????????} else {
????????????????????s.push(p); //第一次訪問到該節(jié)點(diǎn)，需要將它重新入棧
????????????????????p = p->right;
????????????????????break;
????????????????}
?
????????????}
????????} while (!s.empty());
????????return result;
????}