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