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

2024-11-15 12:43:22
推荐回答(1个)
回答1:

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

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