面试的时候，难免会遇到一些关于数据结构的面试题。今天我们来学习一下二叉树的经典面试题：已知二叉树的前序遍历顺序为ABDCEGHF，中序遍历顺序为DBAGEHCF，求二叉树的后序遍历.又：设二叉树的中序遍历顺序为DBAGEHCF，后序遍历顺序为DBGHEFCA，求二叉树的前序遍历。如何应对类似的面试题？什么是二叉树？在开始之前，我先多说几句：什么是二叉树？二叉树（BinaryTree）是一种特殊的树，树上的每个节点都具有至多两个子树的树结构，也就是说每个父节点最多长出两个分支。通常这两个子节点被称为左孩子和右孩子。例如：其中A是整个二叉树的根节点，那么B是A的左子节点，C是A的右子节点。我们可以这样用Java语言实现每个节点：/***二叉树节点*/publicclassTreeNode{publiccharvalue;/***左子树*/publicTreeNodeleft;/***右子树*/publicTreeNoderight;}三种遍历方式解决问题之前先明确一下前序遍历、中序遍历、后序遍历三种遍历方式，这样才能打好为以后解决问题打下基础。前序遍历前序遍历是先访问根节点，再访问左子节点，再访问右子节点。上面二叉树的前序遍历的顺序是ABDCEGHF。我们可以用Java语言来实现：publicvoidpreOrder(TreeNodebiTree){System.out.println(biTree.value);if(biTree.left!=null){preOrder(biTree.left);}if(biTree.right!=null){preOrder(biTree.right);}}中序遍历中序遍历是先访问左子节点，再访问根节点，再访问右子节点。上面二叉树的中序遍历的顺序是DBAGEHCF。我们可以用Java语言来实现：publicvoidpreOrder(TreeNodebiTree){if(biTree.left!=null){preOrder(biTree.left);}System.out.println(biTree.value);if(biTree.right!=null){preOrder(biTree.right);}}后序遍历后序遍历是先访问左子节点，再访问右子节点，再访问根节点。上面二叉树的后序遍历的顺序是DBGHEFCA。我们可以用Java语言来实现：publicvoidpreOrder(TreeNodebiTree){if(biTree.left!=null){preOrder(biTree.left);}System.out.println(biTree.value);if(biTree.right!=null){preOrder(biTree.right);}}通过上面的描述可以得出：前序遍历、中序遍历、后序遍历这三种遍历中的“before”、“middle”、“post”都是指访问顺序对于根节点，“前”是先访问根节点，“中”是访问左右中间的根节点，“后”是最后访问根节点。知道了前序遍历顺序，求后序遍历顺序好麻烦，我们回到刚才的第一道面试题：二叉树的前序遍历顺序是ABDCEGHF，而后序遍历订单是DBAGEHCF。找到二叉树的后序遍历。我们的解题思路是先按照前序遍历顺序重构二叉树，然后按照二叉树写出后序遍历顺序。重构二叉树的前序遍历（ABDCEGHF）中第一个节点A一定是根节点，那么在中序遍历（DBAGEHCF）中，节点A的左边（DB）一定是A的左子树节点A，节点A的右边（GEHCF）一定是节点A的右子树，二叉树的初步判断如下：看A的左子树（DB），在前序遍历（ABDCEGHF）,B在前面，说明B是子树的根节点，再看中序遍历（DBAGEHCF），B的左边（D）一定是A的左子树，右边B的side(none)一定是A的右子树。初步判断二叉树是这样的：看A的右子树(GEHCF)，在前序遍历(ABDCEGHF)中，C在最前面，说明C是子树的根节点，再看中序遍历(DBAGEHCF)，C(GEH)的左边一定是C的左子树，C(F)的右边一定是右子树C的子树。二叉树的初步判断是这样的：看C的左子树（GEH），在前序遍历（ABDCEGHF）中，E在最前面，说明E是C的根节点子树。再看中序遍历(DBAGEHCF)，E(G)的左边一定是E的左子树，E(H)的右边一定是E的右子树，最后可以判断二叉树是这样的：后序遍历顺序写起来比较容易。根据二叉树得到的后序遍历顺序为：已知DBGHEFCA中的后序遍历顺序，找前序遍历顺序就这么多了，回到刚才的面试第一题：知道了二叉树的中序遍历顺序为DBAGEHCF，后序遍历顺序为DBGHEFCA，求二叉树的前序遍历。我们的解题思路是先按照中序遍历顺序重构二叉树，然后按照二叉树写出先序遍历顺序。重构二叉树后序遍历（DBGHEFCA）最后一个节点A一定是根节点，那么在中序遍历（DBAGEHCF）中，节点A的左边（DB）一定是节点A的左子树,节点A的右边（GEHCF）一定是节点A的右子树。二叉树的初步判断如下：看A的左子树（DB）。在后序遍历（DBGHEFCA）,B在最后。说明B是子树的根节点，再看中序遍历（DBAGEHCF），B的左边（D）一定是A的左子树，B的右边（none）一定是A的右子树，初步判断二叉树是这样的：看A的右子树（GEHCF），在后序遍历（DBGHEFCA）中，C在末尾，说明C是根节点的子树，再看中序遍历（DBAGEHCF），C的左边（GEH）一定是C的左子树，C的右边（F）一定是C的右子树。二叉树的初步判断是这样的：看C（GEH）的左子树，在后序（DBGHEFCA）中遍历，E在末尾，说明E是子树的根节点，再看中序遍历（DBAGEHCF），E的左边（G）一定是E的左子树，E的右边（H）一定是E的右子树。可以是最后判断二叉树是这样的：先序遍历顺序写起来比较容易。根据二叉树得到的前序遍历顺序为：ABDCEGHF文章持续更新，微信搜索“万猫“学堂”第一时间阅读。关注后回复“电子书”，获取Java必读12篇免费技术书籍。
