试找出满足下列条件的二叉树：1）先序序列与后序序列相同；2）中序序列与后序序列相同；3）先序序列与中序序列相同；4）中序序列与层次序列相同；

Question

试找出满足下列条件的二叉树：
1）先序序列与后序序列相同； 2）中序序列与后序序列相同；
3）先序序列与中序序列相同； 4）中序序列与层次序列相同；

Answer 1

【答案】先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是：“左子树—右子树―根”,根据以上原则,
1）若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树.
2）若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树.
（3）若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树.
（4）若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树