华为校招&实习机试在线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，右孩子 8，8 的右孩子 10，5 的左孩子 3。三层最靠右的结点依次为 5、8、10，总和 23。
> 注：微信原文未提供输入输出描述与样例，本节输入输出描述取自牛客镜像（同系列官方解析）；原文亦无独立样例，三个样例为镜像标注的验证用样例，已全部用参考程序验证。
思路
整体思路：把输入序列当作二叉排序树的后序遍历，从后往前用单调栈重建整棵树——后序倒看先根、再右子树、再左子树，每个数要么成为栈中某个弹出结点的左孩子，要么成为栈顶的右孩子，挂孩子时检查值是否落在父结点的开区间里，任何一步挂不进去就说明序列非法；重建成功后再做一遍"先右后左"的深度优先遍历，每一层第一次遇到的结点就是该层最靠右的结点，把这些强度加起来输出。
1. 初始化：最后一个数是根，允许范围记成开区间 (0, 10^18)，根入栈，这个栈维护的是"还没向左分叉的右脊"。
2. 从倒数第二个数往前扫：弹出所有比当前值大的栈顶结点，最后弹出的那个就是当前值的父结点，当前值挂在它左边，值必须严格落在（父结点下界，父结点值）的开区间里，同时继承父结点的下界、以父结点值为新上界。
3. 一个都没弹出时，当前值作为栈顶的右孩子，值必须严格落在（栈顶值，栈顶上界）的开区间里，继承栈顶值为下界、栈顶上界为上界。
4. 任何区间检查不通过立即判定非法，输出 -1；通过则当前下标入栈。
5. 重建成功后用显式栈做先右后左遍历：弹出结点时若该深度首次被访问则计入总和，然后先压左孩子再压右孩子，保证右子树整棵先于左子树被访问。
6. 边界：只有一个数时循环不执行，右缘就是它自己；序列含重复值或违反 BST 大小关系都会在区间检查处被判非法。
7. 精度：m 最大 10000、单个强度最大 10^9，总和最大约 10^13，64 位整数足够，但会超过 32 位整数范围。
复杂度：时间 O(m)——每个下标最多进栈出栈一次，轮廓遍历也只经过每个结点一次；空间 O(m)——左右孩子数组、区间边界数组和遍历栈。
Code
C++
/* 脉冲后序右侧和：后序序列用单调栈重建 BST 并校验，再先右后左遍历累加每层最右结点 */ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vector<long long> seq; long long x; /* 整段强度可能在同一行，也可能跨行，按空白逐个读完全部 */ while (cin >> x) seq.push_back(x); int m = (int)seq.size(); vector<int> left(m, -1), right(m, -1); vector<long long> low(m), high(m); int root = m - 1; /* 强度都是正数，根的允许区间用开区间 (0, 10^18) */ low[root] = 0; high[root] = (long long)1e18; vector<int> 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); } /* 先右后左走一遍：某一层第一次遇到的结点就是该层最靠右的结点 用显式栈而不是递归，防止树退化成链时递归过深 */ vector<long long> seen(m, -1); long long total = 0; vector<pair<int, 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)); List<Long> 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; Deque<Integer> 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; Deque<int[]> 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; }Python
def 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()
