遍历结果推导二叉树

1、根据前序与中序,推导二叉树。举例来说:前序ABC,中序CAB,由前序直到A为根节点,由中序知道A的左边为左孩子,右边为右孩子。C为左孩子,B为右孩子。

2、思考,由前序和后续,能否退出二叉树?

  前序ABC,后序CBA。由前序ABC知道A为根节点,后面分成两块,每一块都是前序,前面一块为左孩子,后面一块为右孩子。由后序知道A为根节点,前面分成两块,每一块都是后序,前面一块为左孩子,后面一块为右孩子。都是分成两块,对于分成的两块,前面一块元素集合相同,后面一块元素集合相同。注意,集合不考虑元素的顺序。这样,就有两种情况:

  a、前面一块为BC,后面一块为空

  b、前面一块为空,后面一块为BC

  因此,根据前序与后序不能推导出二叉树。

3、思考,前序与后序一定不能推导出二叉树吗?

  考虑,前序ABC,后续BCA,同样道理,分成两块的情况:

  a、前面一块为B,后面一块为C

  b、前面一块为BC,后面一块为空

  c、前面一块为空,后面一块为BC

  分成两块,每一块都是前序或者后序,但是,前序与后序的顺序一定不一样,对于b,c两种情况,前序与后序顺序一样,因此排除,只剩下a情况。推导出唯一的二叉树。

因此,根据前序与后序不能推导出二叉树,但是某些特殊情况下,可以推导出二叉树。

原文地址:https://www.cnblogs.com/nzbbody/p/3450168.html