algorithm - 构造一棵二叉树，使得后序遍历应该给出排序后的结果

Question

我知道二叉搜索树上的中序遍历(向左访问，向根访问，向右访问)会给我一个排序的结果。但是我需要在二叉树上进行后序遍历(向左访问、向右访问、向根访问)，结果应该给我排序后的值。

为了实现这一点，我应该如何构建我的二叉树？

Answer 1

由于根是最后访问的，因此它必须包含最大的项目。由于左子树在右子树之前被访问，所以左子树中的所有项目必须小于右子树中的任何项目。

因此，要构建这样的树，您可以按以下步骤进行:如果插入一个大于根的项目，则该项目成为新的根。如果插入一个小于根但大于左子树根的项，则将其插入右子树。否则将其插入左子树。