GATE | GATE CS 2013 |问题43

二叉搜索树的前序遍历序列是30、20、10、15、25、23、39、35、42。以下哪一项是同一棵树的后序遍历序列？ （A） 10, 20, 15, 23, 25, 35, 42, 39, 30 （B） 15, 10, 25, 23, 20, 42, 35, 39, 30 （C） 15, 20, 10, 23, 25, 42, 35, 39, 30 （D） 15, 10, 23, 25, 20, 35, 42, 39, 30 答复: （D） 说明： 为了从给定的遍历序列构造二叉树，其中一个遍历序列必须是有序的。另一个遍历序列可以是前序或后序。我们知道二叉搜索树的顺序遍历总是以升序进行的，所以顺序遍历将是给定的顺序遍历的升序，即10，15，20，23，25，30，35，39，42。现在我们必须根据给定的顺序和预序遍历构造一棵树。

参考资料： https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/ https://www.geeksforgeeks.org/data-structures-and-algorithms-set-31/

这个解决方案是由 帕鲁尔·夏尔马。

这个问题的小测验