检查给定顺序是否是合法的顺序遍历

Question

如果您有一个包含十个节点的二叉搜索树，存储整数0至9，那么我们如何确定一个顺序不能代表树的后序遍历？我知道根必须是序列中的最后一个，但我无法达到任何模式。伪代码也会很棒！ （这不是作业，为面试练习）

Answer 1

正如你所说，你知道根源是什么。所以你知道每个子树中的值的范围。如果序列（不包括根）不分割成两个序列，一个小于一个大于根，那么它是无效的。如果是这样，你需要递归检查两个子遍历。如果一切正常，那么它是有效的。