会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
后序遍历从后往前看，先是根，然后先进入右子树，再进入左子树。用单调栈按这个次序把孩子挂上，同时检查每个强度是否落在父结点给出的开区间里。能挂成一棵二叉排序树时，再按先右后左走一遍：某一层第一次遇到的结点，就是该层最靠右的那个。把这些强度加起来。中途有结点挂不进去，就说明这段记录不能还原。
- 最后一个数当作根，允许范围先记成开区间 (0,1018)。强度都是正数，所以根一定落在里面。
- 从倒数第二个数往前扫。栈里保持当前还没向左分叉的右脊。比当前值大的结点弹出，当前值挂到最后一个弹出结点的左边；一个都没弹出，就挂到栈顶的右边。
- 挂左边时，值必须大于父结点的下界、小于父结点自己；挂右边时，值必须大于父结点、小于父结点的上界。不满足就返回 −1。
- 只有一个数时循环不执行，右缘就是它自己。
- 用显式栈做先右后左的遍历，避免树退化成链时递归过深。总和用 64 位整数，因为 m 个接近 109 的强度加起来会超过 231−1。
题目内容
星际探索途中，人类撞见一座年代久远的外星通讯塔。坐标靠一串能量脉冲向外发送。科学家确认，这些互不相同的正整数强度，其实按二叉排序树组织，用来加快检索。
接收端拿到的是一整段脉冲。它记录的是这棵树的后序遍历。
宇宙射线会把这段记录弄乱，于是它未必还能还原成合法的二叉排序树。请完成下面这个核心模块：
- 校验： 判断这段强度能否当作某棵合法二叉排序树的后序遍历。
- 解码： 若能够还原，再求出这座塔「右缘轮廓」上的强度总和。
注： 「右缘轮廓」是从树的右侧望过去，每一层最后映入眼帘的那个结点（也就是该层最靠右的结点）所带的强度。
输出： 能还原时，写下右缘轮廓的强度总和；不能还原时，记成 −1。
输入描述
输入格式
数据来自标准输入。
数据范围：
- 序列长度 m：1≤m≤10000
- 每个强度 w：1≤w≤109，且彼此不重复
输出描述
输出格式
- 能够还原时，输出一个整数，即右缘轮廓的强度总和。
- 不能还原时，输出 −1。
样例1
输入：
3 8 6 12 15 10
输出：
37
解释：
这段记录末尾的根是 10。比 10 小的 [3,8,6] 是左子树，比 10 大的 [12,15] 是右子树。还原后的树是：
- 第 0 层最靠右：10
- 第 1 层最靠右：15
- 第 2 层最靠右：12
右缘轮廓总和：10+15+12=37。
样例2
输入：
3 10 5 8
输出：
-1
解释：
根是 8。由最后一个小于 8 的数 5 划出的左段是 [3,10,5]。其中 10>8，破坏了左子树必须更小的规则，所以这段记录不能还原，输出 −1。
样例 3
输入：
4 7 9
输出：
20
解释：
根是 9。4<9、7<9，都落在左子树；又有 4<7，于是 4 挂在 7 的左侧，整棵树一路向左（根 9，左孩子 7，再往左是 4）。从右侧望去，各层可见的强度分别是 9、7、4。
右缘轮廓总和：9+7+4=20。
提示
- 当 m=1 时，序列里只有一个结点，它自己就是合法的根。
- 还原这棵树要在 O(m) 内完成，否则极端形态可能超时。建议用单调栈从叶子往根挂边，以免朴素递归分治退化成 O(m2)，也避免递归过深把调用栈撑爆。
