M30912: 累加树

构建 BST + 右-根-左累加 + BFS 输出, http://cs101.openjudge.cn/practice/30912

给定一个二叉搜索树先序遍历序列，将其转换为一棵累加树，并输出累加树的按层次遍历序列。
累加树和原二叉树形态相同，设原树上结点v在累加树上对应的结点是u，则u的值是原树上所有大于等于v的结点的和。
样例数据如下图所示，原树结点的值在圈内，对应累加树结点的值在圈外
输入
第1行：一个整数n,表示二叉搜索树有n个结点( 1 <= n <= 100)。第2行，n个整数，本行表示二叉搜索树的先序遍历序列。每个整数范围是 [0, 10000]
输出
对应的累加树的按层次遍历序列
样例输入
9
4 1 0 2 3 6 5 7 8
样例输出
30 36 21 36 35 26 15 33 8

解决该问题的思路可以分为三个主要步骤：

重建二叉搜索树（BST）：由于输入的是二叉搜索树的先序遍历序列，可以按照该序列的顺序依次将节点插入到树中，从而还原出原二叉树的结构。
转换为累加树（GST）：累加树的定义是每个节点的值等于原树中大于或等于该节点值的所有节点值之和。在二叉搜索树中，右子树的所有值都大于当前节点，左子树的所有值都小于当前节点。因此，可以通过反向中序遍历（右 -> 中 -> 左）的方式，从大到小遍历所有节点，并使用一个全局累加变量更新每个节点的值。
层次遍历输出：使用队列对转换后的累加树进行广度优先搜索（BFS），即可得到层次遍历序列。

Python 代码实现

python

import sys
from collections import deque

# 定义二叉树节点
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

# 将节点插入到二叉搜索树中
def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

# 累加树转换辅助类
class GSTConverter:
    def __init__(self):
        self.running_sum = 0

    def convert(self, root):
        if not root:
            return
        # 反向中序遍历：先右子树，再当前节点，最后左子树
        self.convert(root.right)
        
        # 累加当前节点的值
        self.running_sum += root.val
        root.val = self.running_sum
        
        self.convert(root.left)

# 层次遍历二叉树
def level_order_traversal(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

def main():
    # 读取标准输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    preorder = [int(x) for x in input_data[1:n+1]]
    
    if n == 0:
        return

    # 1. 重建二叉搜索树
    root = None
    for val in preorder:
        root = insert(root, val)
    
    # 2. 转换为累加树
    converter = GSTConverter()
    converter.convert(root)
    
    # 3. 层次遍历
    ans = level_order_traversal(root)
    
    # 输出结果
    print(*(ans))

if __name__ == '__main__':
    main()

复杂度分析

时间复杂度：
- 重建 BST：在最坏情况下（树退化为链表），插入每个节点需要 $O (n)$ 时间，总时间为 $O (n^{2})$ 。但由于本题 $n \leq 100$ ，该方法在运行时间和空间上都是可行的。
- 转换为累加树：反向中序遍历每个节点仅访问一次，时间复杂度为 $O (n)$ 。
- 层次遍历：每个节点仅入队和出队一次，时间复杂度为 $O (n)$ 。
- 总体时间复杂度在 $O (n^{2})$ 以内，可轻松通过。
空间复杂度： $O (n)$ ，用于存储二叉树的节点和层次遍历时的队列。

思路：根据二叉搜索树的先序遍历构建 BST（递归：第一个元素为根，剩余部分中小于根的在左子树，大于根的在右子树）。然后反向中序遍历（右-根-左）累加遍历过的节点值之和，更新每个节点的值为累加和。最后用 BFS 输出层序遍历。

python

from collections import deque

def solve():
    data = list(map(int, sys.stdin.read().split()))
    n = data[0]
    pre = data[1:]

    def build(l, r):
        if l > r:
            return None
        root = pre[l]
        mid = r + 1
        for i in range(l + 1, r + 1):
            if pre[i] >= root:
                mid = i
                break
        return [root, build(l + 1, mid - 1), build(mid, r)]

    tree = build(0, n - 1)
    total = [0]

    def accum(node):
        if not node:
            return
        accum(node[2])
        total[0] += node[0]
        node[0] = total[0]
        accum(node[1])

    accum(tree)
    q = deque([tree])
    out = []
    while q:
        node = q.popleft()
        out.append(str(node[0]))
        if node[1]:
            q.append(node[1])
        if node[2]:
            q.append(node[2])
    print(" ".join(out))

if __name__ == "__main__":
    import sys
    solve()

M30912: 累加树 ​

M30912: 累加树