刷题笔记合集🔗

二叉树计算

问题描述

小基 有一棵二叉树，她希望由原始二叉树生成一个新的二叉树，使得新二叉树中的每个节点将包含原始树中的左子树和右子树的节点值之和。

左子树表示该节点左侧叶子节点为根节点的一颗新树；右子树表示该节点右侧叶子节点为根节点的一颗新树。

输入格式

输入共 行整数，第 行表示二叉树的中序遍历，第 行表示二叉树的前序遍历，以空格分割。

输出格式

输出 行整数，表示求和树的中序遍历，以空格分割。

样例输入

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

样例输出

0 3 0 7 0 2 0

数据范围

• 节点数
• 节点值范围：

样例	解释说明
样例1	输入给出了一棵二叉树的中序遍历：-3 12 6 8 9 -10 -7 和前序遍历：8 12 -3 6 -10 9 -7 根据这些遍历序列可以重建原始二叉树 新的求和树中，每个节点的值为其左右子树节点值之和 对这个新的求和树进行中序遍历，得到：0 3 0 7 0 2 0

题解

这道题目要求我们根据给定的中序遍历和前序遍历序列，重建一棵二叉树，然后生成一棵新的二叉树，其中每个节点的值是原始树中左子树和右子树的节点值之和。最后输出这棵新树的中序遍历序列。

首先回顾几个基本概念：

• 中序遍历（左-根-右）：先遍历左子树，再访问根节点，最后遍历右子树
• 前序遍历（根-左-右）：先访问根节点，再遍历左子树，最后遍历右子树

解题思路如下：

1. 根据中序遍历和前序遍历重建原始二叉树

   • 前序遍历的第一个元素是根节点
   • 在中序遍历中找到根节点的位置，其左边是左子树，右边是右子树
   • 递归处理左右子树

2. 在重建树的过程中，同时计算每个节点的左右子树节点值之和

3. 对新生成的树进行中序遍历并输出结果

重建二叉树时需要注意一个细节：当树中存在重复节点值时，我们需要确保正确找到对应的节点。我们可以通过比较左右子树的元素是否匹配来确定正确的根节点位置。

时间复杂度分析：假设树有n个节点，重建树的时间复杂度为O(n²)，因为对于每个节点，我们可能需要O(n)的时间在中序遍历中找到它的位置。空间复杂度为O(n)，用于存储树结构和遍历结果。

这个时间复杂度对于题目给出的数据范围（最多100个节点）是可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

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

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

def build_tree(inorder, preorder, in_start, in_end, pre_start, pre_end):
    """根据中序和前序遍历重建二叉树，同时计算子树和"""
    if pre_start > pre_end:
        return None
    
    # 前序遍历的第一个元素是根节点
    root_val = preorder[pre_start]
    root = TreeNode(root_val)
    
    # 在中序遍历中找到根节点的位置
    root_idx = -1
    for i in range(in_start, in_end + 1):
        if inorder[i] == root_val:
            # 验证这个位置是否正确
            left_size = i - in_start
            # 比较前序中的左子树是否和中序中的左子树匹配
            if left_size > 0:
                left_match = True
                left_in = sorted(inorder[in_start:i])
                left_pre = sorted(preorder[pre_start+1:pre_start+1+left_size])
                if left_in != left_pre:
                    left_match = False
                
                # 比较右子树
                right_match = True
                if i < in_end:
                    right_in = sorted(inorder[i+1:in_end+1])
                    right_pre = sorted(preorder[pre_start+1+left_size:pre_end+1])
                    if right_in != right_pre:
                        right_match = False
                
                if left_match and right_match:
                    root_idx = i
                    break
            else:
                root_idx = i
                break
    
    if root_idx == -1:
        return None
    
    # 计算左右子树大小
    left_size = root_idx - in_start
    
    # 递归构建左右子树
    left_tree = build_tree(
        inorder, preorder, 
        in_start, root_idx - 1, 
        pre_start + 1, pre_start + left_size
    )
    
    right_tree = build_tree(
        inorder, preorder, 
        root_idx + 1, in_end, 
        pre_start + left_size + 1, pre_end
    )
    
    # 连接左右子树
    root.left = left_tree
    root.right = right_tree
    
    # 计算子树和
    left_sum = 0
    right_sum = 0
    
    if left_tree:
        left_sum = left_tree.val + left_tree.sum_val
    
    if right_tree:
        right_sum = right_tree.val + right_tree.sum_val
    
    root.sum_val = left_sum + right_sum
    
    return root

def get_inorder_sum(node, result):
    """获取新树的中序遍历"""
    if not node:
        return
    
    get_inorder_sum(node.left, result)
    result.append(node.sum_val)
    get_inorder_sum(node.right, result)

# 构建树并计算子树和
root = build_tree(inorder, preorder, 0, len(inorder) - 1, 0, len(preorder) - 1)

# 获取新树的中序遍历
result = []
get_inorder_sum(root, result)

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

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 二叉树节点定义
struct TreeNode {
    int val;        // 原始节点值
    int sum_val;    // 左右子树节点值之和
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), sum_val(0), left(nullptr), right(nullptr) {}
};

// 检查两个数组是否包含相同的元素（忽略顺序）
bool check_equal(const vector<int>& vec1, int start1, int end1, 
                 const vector<int>& vec2, int start2, int end2) {
    if (end1 - start1 != end2 - start2) return false;
    
    vector<int> tmp1(vec1.begin() + start1, vec1.begin() + end1 + 1);
    vector<int> tmp2(vec2.begin() + start2, vec2.begin() + end2 + 1);
    
    sort(tmp1.begin(), tmp1.end());
    sort(tmp2.begin(), tmp2.end());
    
    return tmp1 == tmp2;
}

// 根据中序和前序遍历重建二叉树
TreeNode* build_tree(const vector<int>& inorder, const vector<int>& preorder, 
                    int in_start, int in_end, int pre_start, int pre_end) {
    if (pre_start > pre_end) return nullptr;
    
    // 前序遍历的第一个元素是根节点
    int root_val = preorder[pre_start];
    TreeNode* root = new TreeNode(root_val);
    
    // 在中序遍历中找到根节点的位置
    int root_idx = -1;
    
    for (int i = in_start; i <= in_end; ++i) {