30秒解出已知先/后序遍历与中序遍历求出后/先序遍历

看完下面这个方法会让你心生四字
卧槽，牛逼！！！

  画不多说，直奔主题，在昨天晚上室友做题时做到这种已知先/后序与中序遍历，让你求出后／先序遍历，最开始我采用的仍然是老办法，根据先序或者后序的结果确定根节点，在看中序结果，根据根节点在中序的位置，求出左右子树，然后递归求解剩下的节点，画出二叉树。

  那么既然说到30秒写出答案，上面这种方法直接丢掉，接下来就是见证奇迹的时刻。
拿题说话：
第一种情况：已知先序中序求后序：

 
我们只需画一个矩阵：

纵轴从上到下写出先序遍历结果，横轴从左往右写出中序遍历结果，然后把纵轴和横轴对应的字母写出来，谁在最上面谁就是双亲节点，在该字母左边的就是该字母的左子树，右边就是右子树。就比如上面这道题。

矩阵图如下：

  按照上述方法写出先序遍历结果以及中序遍历结果后，s对s，t对t，u对u，w对w，v对v，在矩阵中写出来，然后先后连接，二叉树就完美的画出来了，自然而然后序的结果就是：wuvts。写到这里是不是感觉这个方法异常的流批。

那么有人就会有疑问，为什么v要连接t而不是w呢，上面说到，在图中，处在节点左边的就是该节点的左子树，右边就是右子树，v在t的右边，那么就是t的右子树，所以t和v连接。
还有就是要注意u在w的上面，所以t先连接u，w在u的右下边就是u的右子树在连u。在做题的时候矩阵对应的字母先后顺序一定要画准确，最好用个带格格的纸。

第二种情况：已知中序后序求先序

        方法完全一样，只需把后序遍历的结果按照从后往前的顺序写出来。
      拿题说话：

矩阵图：

 和已知先序遍历唯一的不同就是纵轴的顺序，是按照后序遍历结果从后往前自上到下写下来。

总结：

方法简单粗暴，注意的点就是矩阵图画准确，明确在图中节点左边就是该节点左子树，右边就是右子树。以及注意图中节点上下位置，在该节点上方就是该节点的双亲节点，在下方就是孩子节点，同一行就是兄弟节点。

码字不易，记得点赞收藏哦！！！