二叉树的遍历（递归+迭代）

二叉树的遍历也是数据结构考试以及IT面试的常考点，前序，中序，后续遍历很多人都分不清楚到底是先遍历根节点还是先遍历左孩子呢？实际上所谓的前后中序都是以根节点相对左右孩子节点的遍历顺序为基准的，左右孩子的相对遍历顺序固定，即先遍历左孩子然后再右孩子，根节点在前，则为前序，根节点在左孩子和右孩子的中间，则为中序，根节点的遍历顺序在右孩子后面则为后序。三种遍历方式既可以用递归实现，也可以用迭代实现。

二叉树节点

 1 struct TreeNode {
 2     int val;
 3     struct TreeNode *left;
 4     struct TreeNode *right;
 5     TreeNode(int x) :
 6             val(x), left(NULL), right(NULL) {
 7     }
 8     TreeNode():
 9             val(0),left(NULL),right(NULL){
10     }
11 };

递归版本

前序遍历

1 void TraversePre(TreeNode *root){
2     if(root!=NULL){
3        printf("%d, ",root->val);
4        TraversePre(root->left);
5        TraversePre(root->right);
6     }
7 }

中序遍历

1 void Solution::TraverseMid(TreeNode *root){
2     if(root!=NULL){
3        TraversePre(root->left);
4        printf("%d, ",root->val);
5        TraversePre(root->right);
6     }
7 }

后序遍历

1 void Solution::TraversePost(TreeNode *root){
2     if(root!=NULL){
3        TraversePre(root->left);
4        TraversePre(root->right);
5        printf("%d, ",root->val);
6     }
7 }

迭代版本

前序

每次处理完根节点后，我们可以获得其左孩子树，处理左还孩子节点，因为右子树还没有处理，所以此时需要将根节点压栈来保存根节点。当其左子树为空时，或者说访问完其左子树时，我们将其从栈中取出。一旦从栈中取出某个节点，我们便知该节点已经被访问过了，而且其左子树也被访问过了，我们只要访问其右子树就好了。获得其右子树后，该根节点就没有必要保存了。当栈为空时，并且正在访问的子树为空时，遍历结束。

 1 void PreTravese(TreeNode *root){
 2     TreeNode *p = root;
 3     stack<TreeNode*> st;
 4     while(!st.empty() || p!=NULL){
 5         if(p!=NULL){
 6               printf("%d, ",p->val);
 7               st.push(p);
 8               p=p->left;
 9         }else{//若p为空，则从vector pop出一个来，因为pop出来的已经访问过了其左子树，访问右子树就好了
10             if(!st.empty()){
11                 p = st.top();12                 p = p->right;
13                 st.pop;
14             }
15         }
16     }
17 }

中序

中序遍历的过程跟前序相似，只是处理根节点的时机不同，前序是处理完根节点再将其压栈，而中序是将其从栈中取出时处理根节点。

 1 void MidTraverse(TreeNode *root){
 2     TreeNode *p = root;
 3     stack<TreeNode*> st;
 4     while(!st.empty() || p!=NULL){
 5         if(p!=NULL){
 6               st.push(p);
 7               p=p->left;
 8         }else{//若p为空，则从vector pop出一个来，因为pop出来的已经访问过了其左子树，访问右子树就好了
 9             if(!st.empty()){
10                 p = st.top();
11                 printf("%d, ",p->val);
12                 p = p->right;
13                 st.pop();
14             }
15         }
16     }
17 }

后序

后续遍历比前两者要麻烦一点，根节点需要压栈两次，第一次是因为取出左孩子后，右孩子还没有访问，第二次是取出右孩子自身还没有访问。因此当从一个栈中取出一个根节点时，有两种情景，其一是右孩子没有访问，取出根节点获取右孩子，其二是右孩子已经访问，取出根节点处理根节点本身。而对于同样的出栈操作，没有任何信息是可以区分这两种情景的，因此压栈时需要对根节点做标记，标记其右孩子是否已经被访问过，可以设置一个指针，保存最近处理的节点。

void PostTraverse(TreeNode *root){
    TreeNode *p = root;
    stack<TreeNode*> st;
    st.push(p);
    TreeNode* last==NULL;
    while(!st.empty()){
         p = st.top();
         if(p->right!=NULL && p->right!=last){
               st.push(p->right);
               if(p->left!=NULL)
                      st.push(p->left);
         }else if(p->right==NULL && p->left!=NULL &&p->left!=last){
               st.push(p->left);
         }else{
               printf("%d ",p->data);
               last = p;
               st.pop();
         }
    }
}

Bingo,go,go,go!