traversal - 检查给定的订单是否是合法的后序遍历

Question

如果你有一个有十个节点的二叉搜索树，存储整数 0 到 9，我们如何判断一个序列是否不能代表树的后序遍历？我知道根必须是序列中的最后一个，但我无法得出任何模式。伪代码也很棒！（不是作业，练习面试）

Answer 1

正如你所说，你知道根是什么。所以你知道每个子树中值的范围。如果序列，减去根，没有分成两个序列，一个小于根，一个大于根，那么它是无效的。如果是，则需要递归检查两个子遍历。如果一切正常，那么它是有效的。