算法创作 | 二叉树遍历问题解决方法

我们先看一个简单二叉树来了解它的概念。

所谓前序，中序，后序就是指根所在的位置。比如前序遍历可以理解成根在前，简记成根-左-右。中序遍历可以理解成根在中间，简记成左-根-右。同理后序遍历即左-右-根。

知道这个简单记忆方法后我们再来看一个稍微复杂的二叉树。

要想求解这个二叉树的前序遍历、中序遍历、后序遍历显然比刚才的简单二叉树更难，但是运用原理是一样的。

那么我们是怎么得到它的前序遍历呢？分为5个步骤：

（1）根据口诀，前序就是根在前，即根左右（2）再从上往下把这个二叉树拆解成“ABC”“BEF” “CGH”三棵简单的二叉树（3）确定大范围，从上往下是（根左右）：AB______C_______（4）再锁定到拆解成的另外两棵树“BEF” “CGH”,注意这两棵树的顺序是先左后右，所以先看“BEF”。可以确定在这棵简单二叉树里它的前序就是BEF。根据先左后右，再看树“CGH”，可以确定在这棵简单二叉树里它的前序就是CGH。(5)现在我们已经确定每棵树的前序，那么就可以直接回填了，即AB_EF_____C_GH______

同理，我们怎么得到它的中序遍历呢？同样分成5个步骤：

（1）根据口诀，中序就是根在中间，即左根右（3）确定大范围，从上往下是（左根右）：___B___A___C___(4) 再锁定到拆解成的另外两棵树“BEF” “CGH”,注意这两棵树的顺序是先左后右，所以先看“BEF”。可以确定在这棵简单二叉树里它的中序就是EBF。根据先左后右，再看树“CGH”，可以确定在这棵简单二叉树里它的中序就是GCH。(5)现在我们已经确定每棵树的前序，那么就可以直接回填了，即

__E_B_F__A_G__C__H_

那么最后我们怎么得到它的后序遍历呢？同样用5个步骤来看：

（1）根据口诀，后序就是根在最后，即左右根（2）再从上往下把这个二叉树拆解成“ABC”“BEF” “CGH”三棵简单的二叉树（3）确定大范围，从上往下是（左右根）：

____B____CA(4) 再锁定到拆解成的另外两棵树“BEF” “CGH”,注意这两棵树的顺序是先左后右，所以先看“BEF”。可以确定在这棵简单二叉树里它的后序就是EFB。根据先左后右，再看树“CGH”，可以确定在这棵简单二叉树里它的后序就是GHC。(5)现在我们已经确定每棵树的前序，那么就可以直接回填了，即_EF___B_GH___CA

到这里，它的前序遍历、中序遍历、后序遍历就全部求解完成了。