二叉树的前、中、后序遍历通用方法

首先给大家复习一下前序、后序、中序是怎么一个遍历顺序。你要记忆的话也很好记，对于一个二叉树的节点，除去父节点那它和他相关的一共就只有左节点、右节点和当前节点（中）三个节点。而不管前、中、后序都是左节点比右节点先遍历，中节点在哪儿就是什么遍历。比如中节点在左右节点中间就叫中序遍历（左中右），在左右节点后面就叫后序遍历（左右中）。

递归：

只要是二叉树，基本上都能用递归来解，因为二叉树它的结构很好地满足了递归的要求。递归的思想就是把原有的一个大问题分成若干个具有相同解法的小问题来求解。把要求解的二叉树想成要求解的大问题，那么求解它的左右子树就是在求解小问题，并且它的左右子树依然具有二叉树的性质也就是具有相同的解法，这不就和递归的思想不谋而合吗？

确定了用递归来求解，那就需要考虑终止条件了，也就是我们不停地往下遍历，什么时候该停止？这个简单，我们自然地可以想到当遇到了空节点的时候就该停止然后往回走了。

OK，只要终止条件确定好了，接下来就是递归的常规操作了，以中序遍历为例，直接上代码！
C++实现：

void inorder(TreeNode* cur,vector<int>& ret){
        if(cur==NULL)//终止条件
            return;
        //可替换部分-开始
        inorder(cur->left,ret);//递归左子树
        ret.push_back(cur->val);
        inorder(cur->right,ret);//递归右子树
        //可替换部分-结束
    }
vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorder(root,ret);
        return ret;
    }

Python实现：

def postorderTraversal(root):
        def postorder(cur,ret):
            if cur==None:
                return
            #可替换部分-开始
            postorder(cur.left,ret)#递归左子树
            ret.append(cur.val)
            postorder(cur.right,ret)#递归右子树
            #可替换部分-结束
        
        ret=[]
        postorder(root,ret)
        return ret

递归的方法只要思路理通了实现就很容易，使用上面的代码来实现前序和后序遍历只需要把代码当中的可替换部分中的 ret.push_back(cur->val);放到inorder(cur->left,ret);的前面就实现了前序遍历，放到inorder(cur->right,ret);的后面就实现了后续遍历。原理也很简单，无非就是当前节点是否应该先比它的左或右子节点放到遍历结果当中，该就放在前面，不该就放在后面。

迭代：

要知道，系统实现递归是通过栈来实现的，所以我们也一定可以用栈这种数据结构来实现。可问题在于我们要区分还没有遍历左右子树的节点和已经遍历过左右子树的节点，仅有后者才该进行出栈操作。只把节点入栈让我们难以区分，那么我们就多带点信息进去嘛，这里我是多带了一个bool值，用来区分该节点是不是第一次入栈还是左右节点都已经入栈过再次遇到该退栈这两种情况。先上中序遍历代码：
C++：

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;//返回值
        stack<pair<TreeNode*,bool>> node_stack;//维护整个过程的栈，bool值代表是否其左右子节点还没有入栈
        pair<TreeNode*,bool> tmp;//用来接收每次从栈顶弹出来的值
        //如果根节点不是空就该先入栈，是空的话因为栈也是空所以会直接跳过下面的循环
        if(root!=NULL)
            node_stack.push(pair<TreeNode*,bool>(root,true));
        while(!node_stack.empty()){//当栈退为空的时候代表整棵树已经遍历完成
            //获取栈顶元素
            tmp=node_stack.top();
            node_stack.pop();//将栈顶元素弹出，不能tmp=node_stack.pop()，因为该函数没有返回值
            //可替换部分-开始
            if(tmp.second){//获取bool值，即判断是否其左右子节点还没有入过栈，true代表还没有
                if(tmp.first->right!=NULL)//右子节点不为空，就该入栈进一步处理
                    node_stack.push(pair<TreeNode*,bool>(tmp.first->right,true));//当前节点重新入栈，但bool值改为false
                node_stack.push(pair<TreeNode*,bool>(tmp.first,false));
                if(tmp.first->left!=NULL)//左节点不为空，就该入栈
                    node_stack.push(pair<TreeNode*,bool>(tmp.first->left,true));
            }
            //可替换部分-结束
            else//表示其左右节点已经是入过栈了，该把它的值放到结果当中了
                ret.push_back(tmp.first->val);
        }
        return ret;
    }

Python：

def inorderTraversal(root):
        ret,stack=[],[]#用列表来模拟栈，只要操作符合栈的操作就可以了
        #根节点是否为空，若为空则该不该入栈，就可以跳过下面的循环然后返回
        if root!=None:
            stack.append((root,True))
        while len(stack)!=0 :#当这个栈为空的时候意味着遍历结束
            cur,flag=stack.pop()
            #可替换部分-开始
            if flag:#左右子节点还没有入过栈，先将其入栈
                if cur.right!=None:#先右节点入栈
                    stack.append((cur.right,True))
                stack.append((cur,False))#将当前节点重新入栈，bool值改为False
                if cur.left!=None:#最后是左节点入栈
                    stack.append((cur.left,True))
             #可替换部分-结束
            else:#当前节点左右子节点已经如果栈，所以将值放入遍历结果当中
                ret.append(cur.val)
        return ret

上面是中序遍历的一个实现，但是在代码里面确实先入栈的右节点然后是当前节点，最后才是左节点，这是因为栈是先访问栈顶元素，我们中序遍历顺序是“左中右”所以压入栈的时候就该反着来，这样出栈时候的顺序才和中序遍历要求的一致。

可能大家就要问了，既然我们是用的栈来模拟递归，那为啥递归的时候没有按着相反的顺序来调用？因为递归里面新调用一个函数是放在栈顶的，它只有把栈顶的函数处理完了才会继续处理后面调用的函数，也就是说我们这里用栈来模拟是一下子把三个要处理的都放了进去所以才要反着来以保证左子树在最上面（中序），而递归那里是处理完了左子树再处理当前节点，处理完了当前节点再处理右子树，也就不存在利用栈来模拟时的问题啦！

上面的代码要换成前序和后序也很简单，直接把上面代码的可替换部分，也就是压栈的那一部分的顺序改一下就是了，不过也要注意，入栈和出栈的顺序是相反的，前序的压栈顺序应该是右左中，后序的压栈顺序应当是中右左。

C++的实现里面用到了stack和pair两种数据结构

对于stack它通过stack<type> obj来创建一个栈，在本例中它还用到了：obj.top()用来获取栈顶元素，obj.pop()将栈顶元素弹出（这个与Python的pop()不同，Python中的是弹出且返回其值，而C++的并不会返回），obj.push(x)将x元素压入栈顶
对于pair它是一个键值对，初始化用pair<type1 type2> obj在本例中它还使用了：obj.first用来访问键值对的键，obj.second用来访问值