E卷-二叉树计算(200分)

二叉树计算

问题描述

给定一个二叉树，请生成一个新的二叉树，使得新树中的每个节点的值等于原始树中该节点的左子树和右子树所有节点值的和。左子树表示该节点左侧叶子节点为根节点的一颗新树；右子树表示该节点右侧叶子节点为根节点的一颗新树。

原始二叉树：

    6
   / \
  7   9
 /   / \
-2  6   -7

生成的新二叉树：

    20
   /  \
  -2   8
 /    / \
0    0   0

解释：

1. 根节点 6 变为 20，因为它的左子树和右子树所有节点值的和为 7 + (-2) + 9 + 6 + (-7) = 20。
2. 左子节点 7 变为 -2，因为它只有一个左子节点，值为 -2。
3. 右子节点 9 变为 8，因为它的左右子节点值的和为 6 + (-7) = -1。
4. 所有叶子节点变为 0，因为它们没有子节点。

输入格式

输入包含两行整数：

• 第一行表示二叉树的中序遍历序列，以空格分隔。
• 第二行表示二叉树的前序遍历序列，以空格分隔。

输出格式

输出一行整数，表示生成的新二叉树（求和树）的中序遍历序列，以空格分隔。

样例输入1

7 -2 6 6 9
6 7 -2 9 6

样例输出1

-2 0 20 0 6

样例输入2

-3 12 6 8 9 -10 -7
8 12 -3 6 -10 9 -7

样例输出2

0 3 0 7 0 2 0

样例解释

数据范围

• 二叉树的节点数量 满足
• 每个节点的值 满足

题解

模拟

这道题目的核心在于理解二叉树的遍历特性和如何利用中序遍历和前序遍历重建二叉树。解题步骤如下：

1. 首先，需要根据给定的中序遍历和前序遍历序列重建原始二叉树。这是因为只有重建出原始树的结构，才能正确计算每个节点的子树和。

2. 重建二叉树的关键在于理解前序遍历和中序遍历的特点：

   • 前序遍历的第一个元素总是树的根节点。
   • 在中序遍历中，根节点左边的元素属于左子树，右边的元素属于右子树。

3. 利用这些特点，可以递归地重建二叉树：

   • 从前序遍历中取第一个元素作为当前子树的根。
   • 在中序遍历中找到这个根元素，将序列分为左右两部分。
   • 递归地处理左右子树。

4. 在重建树的过程中，同时计算每个节点的子树和。这可以通过在节点结构中添加一个额外的字段来实现。

5. 最后，对重建并计算好子树和的树进行中序遍历，输出结果。

参考代码

• Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val        # 节点值
        self.left = left      # 左子节点
        self.right = right    # 右子节点
        self.child_sum = 0    # 子树和

def build_tree(inorder, preorder):
    if not inorder or not preorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    root_index = inorder.index(root_val)
    
    # 分割中序遍历
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index + 1:]
    
    # 分割前序遍历
    left_preorder = preorder[1:1 + len(left_inorder)]
    right_preorder = preorder[1 + len(left_inorder):]
    
    # 递归构建左右子树
    root.left = build_tree(left_inorder, left_preorder)
    root.right = build_tree(right_inorder, right_preorder)
    
    # 计算子树和
    root.child_sum = sum(left_inorder) + sum(right_inorder)
    
    return root

def get_mid_order(root):
    if not root:
        return []
    # 中序遍历：左 -> 根 -> 右
    return get_mid_order(root.left) + [root.child_sum] + get_mid_order(root.right)

# 读取输入
inorder = list(map(int, input().split()))
preorder = list(map(int, input().split()))

# 构建树并获取结果
root = build_tree(inorder, preorder)
result = get_mid_order(root)

# 输出结果
print(' '.join(map(str, result)))

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 10001

typedef struct TreeNode {
    int val;
    int child_sum;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int inorder[MAX_N], preorder[MAX_N];
int n, idx;

// 构建树的函数
TreeNode* build_tree(int in_start, int in_end, int pre_start, int pre_end) {
    if (in_start > in_end) return NULL;
    
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = preorder[pre_start];
    root->child_sum = 0;
    root->left = root->right = NULL;
    
    // 在中序遍历中找到根节点的位置
    int root_idx;
    for (root_idx = in_start; root_idx <= in_end; root_idx++) {
        if (inorder[root_idx] == root->val) break;
    }
    
    int left_size = root_idx - in_start;
    
    // 递归构建左右子树
    root->left = build_tree(in_start, root_idx - 1, pre_start + 1, pre_start + left_size);
    root->right = build_tree(root_idx + 1, in_end, pre_start + left_size + 1, pre_end);
    
    // 计算子树和
    for (int i = in_start; i < root_idx; i++) root->child_sum += inorder[i];
    for (int i = root_idx + 1; i <= in_end; i++) root->child_sum += inorder[i];
    
    return root;
}

// 中序遍历输出结果
void get_mid_order(TreeNode* root) {
    if (!root) return;
    get_mid_order(root->left);
    printf("%d ", root->child_sum);
    get_mid_order(root->right);
}

int main() {
    char line[MAX_N * 10];
    // 读取中序遍历
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, " \n");
    while (token) {
        inorder[n++] = atoi(token);
        token = strtok(NULL, " \n");
    }
    
    // 读取前序遍历
    fgets(line, sizeof(line), stdin);
    token = strtok(line, " \n");
    idx = 0;
    while (token) {
        preorder[idx++] = atoi(token);
        token = strtok(NULL, " \n");
    }
    
    // 构建树并输出结果
    TreeNode* root = build_tree(0, n - 1, 0, n - 1);
    get_mid_order(root);
    printf("\n");
    
    retu