会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
后序遍历从后往前看，先是根，然后先进入右子树，再进入左子树。用单调栈按这个次序把孩子挂上，同时检查每个强度是否落在父结点给出的开区间里。能挂成一棵二叉排序树时，再按先右后左走一遍：某一层第一次遇到的结点，就是该层最靠右的那个。把这些强度加起来。中途有结点挂不进去，就说明这段记录不能还原。
- 最后一个数当作根，允许范围先记成开区间 (0,1018)。强度都是正数，所以根一定落在里面。
- 从倒数第二个数往前扫。栈里保持当前还没向左分叉的右脊。比当前值大的结点弹出，当前值挂到最后一个弹出结点的左边；一个都没弹出，就挂到栈顶的右边。
- 挂左边时，值必须大于父结点的下界、小于父结点自己；挂右边时，值必须大于父结点、小于父结点的上界。不满足就返回 −1。
- 只有一个数时循环不执行，右缘就是它自己。
- 用显式栈做先右后左的遍历，避免树退化成链时递归过深。总和用 64 位整数，因为 m 个接近 109 的强度加起来会超过 231−1。
