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