Question

二叉树 已知两个遍历顺序 求第另一种遍历顺序 并且要求画出二叉树，要怎么解决这种题目呀?

Answer 1

1.假设知道前序跟中序：前序序列中的第一个数就是根，然后在中序序列里面找到这个数，就把该中序序列分成两半，左边是根的左子树，右边是根的右子树，在前序序列里面找到相应的左右子树，重复递归！
2.假设知道中序跟后序：原理差不多，在后序序列里面的最后一个数是根，在中序序列里面找到这个数把该序列分成两半，左边是左子树右边是右子树，在后序序列找到相应的左右子树，重复递归！
知道前序跟后序貌似无法知道中序序列！

这里要留意没有左子树或者右子树的情况，比如第一种情况，在前序中找到根之后，在中序序列中发现左边或者右边没有数了，就表示该根没有左子树或者右子树