是否有可能中序遍历与post序遍历的顺序相同？

Question

例如，假设 T 是一棵二叉树：

T的中序遍历是否可以和T的后序遍历相同？如果 "yes" 你能举个例子吗？如果 "No" 你能解释一下为什么它不会发生吗？

另外，T的中序遍历是否可以和T的前序遍历相同？

在此先感谢您。

Answer 1

可能吗？是的。考虑如下树的中序、前序、后序遍历

A

...即只有一个节点组成的树，没有children.

这棵树的中序、前序、后序遍历如下：[A].

一般来说，如果只有左children，中序遍历就相当于后序遍历，只有右children，中序遍历就相当于前序遍历。

Answer 2

1. T的中序遍历是否可以和 后序遍历T?

是的，当树的每个节点只有左 child 时：

                     a
                    / \
                   b  null
                  / \
                 c  null
                / \
               ...

2. T的中序遍历是否可以和 预序遍历T?

是的，当树在每个节点只有一个权利child时：

                     a
                    / \
                 null  b
                      / \
                   null  c
                        / \
                         ...

查看 here 以获得更详细的解释。