华为校招实习机试在线OJ刷题系统 在线OJ注册使用教程目录题目思路Code题目题目内容星际探索途中人类撞见一座年代久远的外星通讯塔。坐标靠一串能量脉冲向外发送。科学家确认这些互不相同的正整数强度其实按二叉排序树组织用来加快检索。接收端拿到的是一整段脉冲。它记录的是这棵树的后序遍历。宇宙射线会把这段记录弄乱于是它未必还能还原成合法的二叉排序树。请完成下面这个核心模块- 校验判断这段强度能否当作某棵合法二叉排序树的后序遍历。- 解码若能够还原再求出这座塔「右缘轮廓」上的强度总和。注「右缘轮廓」是从树的右侧望过去每一层最后映入眼帘的那个结点也就是该层最靠右的结点所带的强度。输出能还原时写下右缘轮廓的强度总和不能还原时记成 −1。数据范围序列长度 m ≤ 10000单个强度不超过 10⁹。输入格式一行若干个互不相同的正整数用空格隔开表示整段强度即二叉树的后序遍历序列。输出格式能还原时输出右缘轮廓的强度总和不能还原时输出 −1。样例1输入3 10 8 5输出23样例2输入3 1 2 1 2 3输出-1 6样例说明后序 3 10 8 5 还原出的二叉排序树为根 5右孩子 88 的右孩子 105 的左孩子 3。三层最靠右的结点依次为 5、8、10总和 23。 注微信原文未提供输入输出描述与样例本节输入输出描述取自牛客镜像同系列官方解析原文亦无独立样例三个样例为镜像标注的验证用样例已全部用参考程序验证。思路整体思路把输入序列当作二叉排序树的后序遍历从后往前用单调栈重建整棵树——后序倒看先根、再右子树、再左子树每个数要么成为栈中某个弹出结点的左孩子要么成为栈顶的右孩子挂孩子时检查值是否落在父结点的开区间里任何一步挂不进去就说明序列非法重建成功后再做一遍先右后左的深度优先遍历每一层第一次遇到的结点就是该层最靠右的结点把这些强度加起来输出。1. 初始化最后一个数是根允许范围记成开区间 (0, 10^18)根入栈这个栈维护的是还没向左分叉的右脊。2. 从倒数第二个数往前扫弹出所有比当前值大的栈顶结点最后弹出的那个就是当前值的父结点当前值挂在它左边值必须严格落在父结点下界父结点值的开区间里同时继承父结点的下界、以父结点值为新上界。3. 一个都没弹出时当前值作为栈顶的右孩子值必须严格落在栈顶值栈顶上界的开区间里继承栈顶值为下界、栈顶上界为上界。4. 任何区间检查不通过立即判定非法输出 -1通过则当前下标入栈。5. 重建成功后用显式栈做先右后左遍历弹出结点时若该深度首次被访问则计入总和然后先压左孩子再压右孩子保证右子树整棵先于左子树被访问。6. 边界只有一个数时循环不执行右缘就是它自己序列含重复值或违反 BST 大小关系都会在区间检查处被判非法。7. 精度m 最大 10000、单个强度最大 10^9总和最大约 10^1364 位整数足够但会超过 32 位整数范围。复杂度时间 O(m)——每个下标最多进栈出栈一次轮廓遍历也只经过每个结点一次空间 O(m)——左右孩子数组、区间边界数组和遍历栈。CodeC/* 脉冲后序右侧和后序序列用单调栈重建 BST 并校验再先右后左遍历累加每层最右结点 */ #include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vectorlong long seq; long long x; /* 整段强度可能在同一行也可能跨行按空白逐个读完全部 */ while (cin x) seq.push_back(x); int m (int)seq.size(); vectorint left(m, -1), right(m, -1); vectorlong long low(m), high(m); int root m - 1; /* 强度都是正数根的允许区间用开区间 (0, 10^18) */ low[root] 0; high[root] (long long)1e18; vectorint st {root}; /* 从倒数第二个数往前扫栈里保持当前还没向左分叉的右脊 */ for (int i m - 2; i 0; i--) { long long val seq[i]; int parent -1; /* 弹出所有比当前值大的栈顶结点最后弹出的就是当前值的父结点 */ while (!st.empty() seq[st.back()] val) { parent st.back(); st.pop_back(); } if (parent ! -1) { /* 挂到刚弹出结点的左边值必须严格落在父下界, 父值里 */ if (!(low[parent] val val seq[parent])) { cout -1 \n; return 0; } low[i] low[parent]; high[i] seq[parent]; left[parent] i; } else { /* 没有更大的祖先可挂就作为栈顶的右孩子 */ int p st.back(); /* 挂右边值必须严格落在栈顶值, 栈顶上界里 */ if (!(seq[p] val val high[p])) { cout -1 \n; return 0; } low[i] seq[p]; high[i] high[p]; right[p] i; } st.push_back(i); } /* 先右后左走一遍某一层第一次遇到的结点就是该层最靠右的结点 用显式栈而不是递归防止树退化成链时递归过深 */ vectorlong long seen(m, -1); long long total 0; vectorpairint, int walk {{root, 0}}; while (!walk.empty()) { int u walk.back().first; int dep walk.back().second; walk.pop_back(); if (seen[dep] -1) { seen[dep] seq[u]; total seq[u]; } /* 先压左孩子再压右孩子弹栈时右子树整棵先于左子树被访问 */ if (left[u] ! -1) walk.push_back({left[u], dep 1}); if (right[u] ! -1) walk.push_back({right[u], dep 1}); } cout total \n; return 0; }Java/* 脉冲后序右侧和后序序列用单调栈重建 BST 并校验再先右后左遍历累加每层最右结点 */ import java.util.*; import java.io.*; public class Solution { public static void main(String[] args) throws IOException { /* 用 StreamTokenizer 按空白逐个读数不关心换行位置 */ StreamTokenizer in new StreamTokenizer(new BufferedInputStream(System.in)); ListLong list new ArrayList(); while (in.nextToken() ! StreamTokenizer.TT_EOF) { list.add((long) in.nval); } int m list.size(); long[] seq new long[m]; for (int i 0; i m; i) seq[i] list.get(i); int[] left new int[m], right new int[m]; long[] low new long[m], high new long[m]; Arrays.fill(left, -1); Arrays.fill(right, -1); int root m - 1; /* 强度都是正数根的允许区间用开区间 (0, 10^18) */ low[root] 0; high[root] (long) 1e18; DequeInteger st new ArrayDeque(); st.push(root); /* 从倒数第二个数往前扫栈里保持当前还没向左分叉的右脊 */ for (int i m - 2; i 0; i--) { long val seq[i]; int parent -1; /* 弹出所有比当前值大的栈顶结点最后弹出的就是当前值的父结点 */ while (!st.isEmpty() seq[st.peek()] val) { parent st.pop(); } if (parent ! -1) { /* 挂到刚弹出结点的左边值必须严格落在父下界, 父值里 */ if (!(low[parent] val val seq[parent])) { System.out.println(-1); return; } low[i] low[parent]; high[i] seq[parent]; left[parent] i; } else { /* 没有更大的祖先可挂就作为栈顶的右孩子 */ int p st.peek(); /* 挂右边值必须严格落在栈顶值, 栈顶上界里 */ if (!(seq[p] val val high[p])) { System.out.println(-1); return; } low[i] seq[p]; high[i] high[p]; right[p] i; } st.push(i); } /* 先右后左走一遍某一层第一次遇到的结点就是该层最靠右的结点 用显式栈而不是递归防止树退化成链时递归过深 */ long[] seen new long[m]; Arrays.fill(seen, -1); long total 0; Dequeint[] walk new ArrayDeque(); walk.push(new int[]{root, 0}); while (!walk.isEmpty()) { int[] top walk.pop(); int u top[0], dep top[1]; if (seen[dep] -1) { seen[dep] seq[u]; total seq[u]; } /* 先压左孩子再压右孩子弹栈时右子树整棵先于左子树被访问 */ if (left[u] ! -1) walk.push(new int[]{left[u], dep 1}); if (right[u] ! -1) walk.push(new int[]{right[u], dep 1}); } System.out.println(total); } }Go/* 脉冲后序右侧和后序序列用单调栈重建 BST 并校验再先右后左遍历累加每层最右结点 */ package main import ( bufio fmt os ) func main() { /* 输入可能跨行用 bufio.Reader 按词读bufio.Scanner 默认缓冲对大输入不够 */ reader : bufio.NewReaderSize(os.Stdin, 1024*1024) var seq []int64 for { var x int64 if _, err : fmt.Fscan(reader, x); err ! nil { break } seq append(seq, x) } m : len(seq) left : make([]int, m) right : make([]int, m) low : make([]int64, m) high : make([]int64, m) for i : 0; i m; i { left[i], right[i] -1, -1 } root : m - 1 /* 强度都是正数根的允许区间用开区间 (0, 10^18) */ low[root] 0 high[root] 1e18 st : []int{root} invalid : false /* 从倒数第二个数往前扫栈里保持当前还没向左分叉的右脊 */ for i : m - 2; i 0 !invalid; i-- { val : seq[i] parent : -1 /* 弹出所有比当前值大的栈顶结点最后弹出的就是当前值的父结点 */ for len(st) 0 seq[st[len(st)-1]] val { parent st[len(st)-1] st st[:len(st)-1] } if parent ! -1 { /* 挂到刚弹出结点的左边值必须严格落在父下界, 父值里 */ if !(low[parent] val val seq[parent]) { invalid true break } low[i] low[parent] high[i] seq[parent] left[parent] i } else { /* 没有更大的祖先可挂就作为栈顶的右孩子 */ p : st[len(st)-1] /* 挂右边值必须严格落在栈顶值, 栈顶上界里 */ if !(seq[p] val val high[p]) { invalid true break } low[i] seq[p] high[i] high[p] right[p] i } st append(st, i) } if invalid { fmt.Println(-1) return } /* 先右后左走一遍某一层第一次遇到的结点就是该层最靠右的结点 用显式栈而不是递归防止树退化成链时递归过深 */ seen : make([]int64, m) for i : range seen { seen[i] -1 } var total int64 type node struct { u, dep int } walk : []node{{root, 0}} for len(walk) 0 { top : walk[len(walk)-1] walk walk[:len(walk)-1] u, dep : top.u, top.dep if seen[dep] -1 { seen[dep] seq[u] total seq[u] } /* 先压左孩子再压右孩子弹栈时右子树整棵先于左子树被访问 */ if left[u] ! -1 { walk append(walk, node{left[u], dep 1}) } if right[u] ! -1 { walk append(walk, node{right[u], dep 1}) } } fmt.Println(total) }C/* 脉冲后序右侧和后序序列用单调栈重建 BST 并校验再先右后左遍历累加每层最右结点 */ #include stdio.h #include stdlib.h int main(void) { /* 动态数组收集全部整数输入可能跨行不能按行读 */ int cap 16, m 0; long long *seq malloc(sizeof(long long) * cap); long long x; while (scanf(%lld, x) 1) { if (m cap) { cap * 2; seq realloc(seq, sizeof(long long) * cap); } seq[m] x; } int *left malloc(sizeof(int) * m); int *right malloc(sizeof(int) * m); long long *low malloc(sizeof(long long) * m); long long *high malloc(sizeof(long long) * m); int *st malloc(sizeof(int) * m); /* 手写栈存还没向左分叉的右脊下标 */ int top 0; int root m - 1; /* 强度都是正数根的允许区间用开区间 (0, 10^18) */ low[root] 0; high[root] (long long)1e18; st[top] root; int invalid 0; /* 从倒数第二个数往前扫 */ for (int i m - 2; i 0 !invalid; i--) { long long val seq[i]; int parent -1; /* 弹出所有比当前值大的栈顶结点最后弹出的就是当前值的父结点 */ while (top 0 seq[st[top - 1]] val) { parent st[--top]; } if (parent ! -1) { /* 挂到刚弹出结点的左边值必须严格落在父下界, 父值里 */ if (!(low[parent] val val seq[parent])) { invalid 1; break; } low[i] low[parent]; high[i] seq[parent]; left[parent] i; } else { /* 没有更大的祖先可挂就作为栈顶的右孩子 */ int p st[top - 1]; /* 挂右边值必须严格落在栈顶值, 栈顶上界里 */ if (!(seq[p] val val high[p])) { invalid 1; break; } low[i] seq[p]; high[i] high[p]; right[p] i; } st[top] i; } if (invalid) { printf(-1\n); return 0; } /* 先右后左走一遍某一层第一次遇到的结点就是该层最靠右的结点 手写栈存 (结点, 深度)先压左孩子再压右孩子右子树先被访问 */ long long *seen malloc(sizeof(long long) * m); for (int i 0; i m; i) seen[i] -1; long long total 0; int *wu malloc(sizeof(int) * m); int *wd malloc(sizeof(int) * m); int wtop 0; wu[wtop] root; wd[wtop] 0; wtop; while (wtop 0) { wtop--; int u wu[wtop], dep wd[wtop]; if (seen[dep] -1) { seen[dep] seq[u]; total seq[u]; } if (left[u] ! -1) { wu[wtop] left[u]; wd[wtop] dep 1; wtop; } if (right[u] ! -1) { wu[wtop] right[u]; wd[wtop] dep 1; wtop; } } printf(%lld\n, total); free(seq); free(left); free(right); free(low); free(high); free(st); free(seen); free(wu); free(wd); return 0; }Pythondef right_edge_sum(seq): # 判断后序遍历序列能否还原成二叉排序树能则返回右缘轮廓强度总和不能返回 -1 m len(seq) # 下标从 0 计后序遍历的最后一个数是根 left [-1] * m right [-1] * m low [0] * m # 每个结点允许取值的开区间下界 high [0] * m # 每个结点允许取值的开区间上界 root m - 1 # 强度都是正数根的允许区间用开区间 (0, 10^18) low[root] 0 high[root] 10 ** 18 stack [root] # 从倒数第二个数往前扫栈里保持当前还没向左分叉的右脊 for i in range(m - 2, -1, -1): val seq[i] parent -1 # 弹出所有比当前值大的栈顶结点最后弹出的就是当前值的父结点 while stack and seq[stack[-1]] val: parent stack.pop() if parent ! -1: # 挂到刚弹出结点的左边值必须严格落在父下界, 父值里 if not (low[parent] val seq[parent]): return -1 low[i] low[parent] high[i] seq[parent] left[parent] i else: # 没有更大的祖先可挂就作为栈顶的右孩子 p stack[-1] # 挂右边值必须严格落在栈顶值, 栈顶上界里 if not (seq[p] val high[p]): return -1 low[i] seq[p] high[i] high[p] right[p] i stack.append(i) # 先右后左走一遍某一层第一次遇到的结点就是该层最靠右的结点 # 用显式栈而不是递归防止树退化成链时递归过深 seen [-1] * m walk [(root, 0)] total 0 while walk: u, dep walk.pop() if seen[dep] -1: seen[dep] seq[u] total seq[u] # 先压左孩子再压右孩子弹栈时右子树整棵先于左子树被访问 if left[u] ! -1: walk.append((left[u], dep 1)) if right[u] ! -1: walk.append((right[u], dep 1)) return total def main(): import sys # 整段强度可能跨多行直接按空白切分读全部 seq list(map(int, sys.stdin.read().split())) # 不能还原时函数已经返回 -1 print(right_edge_sum(seq)) if __name__ __main__: main()