我们知道，二叉树有三种常见的遍历方式，分别为前序遍历，中序遍历和后序遍历，如果我们知道其中两种遍历方式，如何求第三种呢？今天我们一起来学习或者回顾一下：
1、 前序遍历二叉树
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：
对于任一结点P：
(1)访问结点P，并将结点P入栈;
(2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
(3)直到P为NULL并且栈为空，则遍历结束。
2、中序遍历二叉树
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于任一结点P，
(1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
(2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
(3)直到P为NULL并且栈为空则遍历结束s
3、后序遍历二叉树
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。
第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
4、已知前序中序求后序
例如，我们前序遍历的顺序为GDAFEMHZ，中序遍历的顺序为ADEFGHMZ。
考虑一下前序遍历的特点，第一个访问的结点肯定是根结点，所以根结点为G，那么对于中序遍历来说，根结点是在左子树遍历完成之后才访问的，所以ADEF位于根结点的左侧，而HMZ位于根结点的右侧。
好了，知道了左子树为ADEF，我们接着看前序遍历的结果，可以看到D为左子树的根结点，所以A在D的左侧，EF在D的右侧。
我们继续看D的左子树A，发现它的左右子树都为空了，我们可以直接打印根结点A。
接下来看D的右子树EF，由前序遍历的结果看，F是根结点，则E位于F的左侧，所以我们接着访问F。
省略下面的思考过程，不过相信大家都明白了，已知前序中序求后序的大体思路就是根据前序的结果判定根结点，再根据中序遍历的结果确定左右子树的结点，如此递归。
步骤如下：
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
5、已知中序后序求前序
依然用上面的例子，不过这次我们知道的是中序和后序的结果：中序遍历:ADEFGHMZ，后序遍历: AEFDHZMG
其实与知道前序和中序求后序的思路一模一样，只不过由前序第一个访问根结点，变成了在后序遍历中最后一个访问根结点，所以大体的思路仍然一样，根据后序遍历结果求根结点，由中序遍历结果确定左右子树的结点，如此递归。
步骤如下：
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
6、已知前序后序求中序
这个的结果是不唯一的，所以一般不会这样问你。
