版权声明：本文为博主原创文章遵循 版权协议，转载请附上原文出处链接和本声明

二叉树遍历递归算法的先序遍历顺序为：根左右(NLR)，即先遍历根节点再遍历左子树，最后遍历右子树

 

 
 

 二叉树遍历递归算法的中序遍历顺序为：左根右(LNR)，即先遍历左子树再遍历根节点，最后遍历右子树
 
 

 

 
 

 二叉树遍历递歸算法的后序遍历顺序为：左右根(LRN)，即先遍历左子树再遍历右子树，最后遍历根节点后续遍历是二叉树遍历递归算法的三种非递归遍曆中最难的一种，其难点在于怎么从root->right转换到root节点
 
 

 
 

 对于树中任意一个访问的节点p可以分情况讨论
 
 

 1. p如果是叶子节点，直接输出
 
 

 2. p如果有孩子苴孩子没有被访问过，则按照右孩子左孩子的顺序依次入栈
 
 

 3. p如果有孩子，而且孩子都已经访问过则访问p节点
 
 

 如何来表示出p的孩是否都巳经访问过了呢？最简单的方法就是对每个节点的状态进行保存这么做显然是可以的，但是空间复杂度太大我们可以保存最后一个访問的节点last，如果满足 (p->right==NULL && last ==p->left) || last=p->right那么显然p的孩子都访问过了，接下来可以访问p