题面描述:

给定一个二叉树的中序遍历和前序遍历，要求生成一个新的二叉树，使得每个节点的值为原始树中其左子树和右子树节点值的总和。输入包含两行整数，第一行为中序遍历，第二行为前序遍历，节点值以空格分隔。输出为新树的中序遍历结果，同样以空格分隔。

思路

1. 理解二叉树遍历：

   • 中序遍历的顺序为：左子树 → 根节点 → 右子树。
   • 前序遍历的顺序为：根节点 → 左子树 → 右子树。
   • 通过这两种遍历方式，可以唯一确定一棵二叉树。

2. 重建二叉树：

   • 从前序遍历的第一个元素可以确定树的根节点。
   • 在中序遍历中找到这个根节点的位置，可以将中序遍历分成左子树和右子树。
   • 根据左子树和右子树的长度，从前序遍历中划分出左子树和右子树的节点。

3. 计算子树和：

   • 在构建树的过程中，需要为每个节点计算其左子树和右子树的节点值之和。
   • 对于每个节点，左子树和右子树的和可以通过递归调用得到。

4. 递归构建：

   • 使用递归函数来构建树，参数包括中序和前序遍历的边界。每次递归都确定当前子树的根节点、左子树和右子树的边界，并在递归返回时计算节点的值。

5. 输出中序遍历结果：

   • 完成树的构建后，使用中序遍历的方法输出新树的节点值。

注意在确立二叉树时前序遍历的第一个节点即是根节点的值但在中序遍历中可能有很多相同值,因此应该对每个值进行讨论，如果以该节点为根节点划分左右子树与在前序遍历中划分左右子树一致即为根节点.

代码解析

1. 输入解析：

   • 使用 splitCin 函数从标准输入中读取两行整数，分别代表中序遍历和前序遍历。

2. 二叉树节点定义：

   • 定义 Nod 结构体，包含节点值 v、左子树和右子树的和 s 以及指向左右子节点的指针。

3. 中序遍历和前序遍历的存储：

   • 使用 vector<int> 存储中序遍历和前序遍历的结果。
   • 使用 map<int, vector<int>> 存储中序遍历中每个节点值的索引，以便在后续构建树时快速查找。

4. 构建二叉树：

   • bT 函数根据中序和前序遍历重建二叉树。该函数通过递归处理，确定每个子树的根节点，并计算其左右子树的和。
   • 在构建过程中，使用 neq 函数检查中序和前序遍历中的节点值出现次数是否一致，以确保构建的正确性。

5. 输出结果：

   • 使用 in 函数进行中序遍历，输出新树的中序遍历结果。

时间复杂度

• 构建树的时间复杂度为 (O(n^2))，在最坏情况下（例如链状树）可能会出现。
• 中序遍历的时间复杂度为 (O(n))，因此整体时间复杂度为 (O(n^2))。

c++

#include <bits/stdc++.h>

using namespace std;

// 输入解析函数
vector<int> splitCin(char sep) {
    string s;
    getline(cin, s);

    stringstream ss(s);
    string tok;

    vector<int> nums;

    while (getline(ss, tok, sep)) {
        nums.emplace_back(stoi(tok));
    }

    return nums;
}

// 二叉树节点定义
struct Nod {
    int v; // 当前节点的值
    int s{0}; // 当前节点的左子树+右子树的和
    Nod *l{};
    Nod *r{};

    explicit Nod(int val) : v(val) {}
};

// 中序遍历序列
vector<int> mo;

// 前序遍历序列
vector<int> po;

// 记录中序遍历序列中，序列元素值所在位置
map<int, vector<int>> mi;

// 二叉树中序遍历
void in(Nod *root) {
    if (!root) return;

    in(root->l);
    cout << root->s << " ";
    in(root->r);
}

// 统计 nums 的 [l, r) 区间内各个元素出现次数
map<int, int> cnt(vector<int> &nums, int l, int r) {
    map<int, int> c;
    for (int i = l; i < r; i++) {
        c[nums[i]]++;
    }
    return c;
}

// 判断两个 map 是否相同
bool neq(int ml, int pl, int sz) {
    auto c1 = cnt(mo, ml, ml + sz);
    auto c2 = cnt(po, pl, pl + sz);

    if (c1.size() != c2.size()) return true;

    for (const auto &p : c1) {
        if (c2[p.first] != p.second) return true;
    }

    return false;
}

/*!
 * 根据中序遍历序列、前序遍历序列还原树结构
 * @param ml 中序遍历子序列的左边界
 * @param mr 中序遍历子序列的右边界
 * @param pl 前序遍历子序列的左边界
 * @param pr 前序遍历子序列的右边界
 * @return 树结构的根节点
 */
Nod *bT(int ml, int mr, int pl, int pr) {
    if (pl > pr) return nullptr;

    int rootVal = po[pl];
    auto *root = new Nod(rootVal);

    for (const auto &idx : mi[rootVal]) {
        if (idx < ml || idx > mr) continue;

        int lLen = idx - ml;
        if (neq(ml, pl + 1, lLen)) continue;

        int rLen = mr - idx;
        if (neq(idx + 1, pr - rLen + 1, rLen)) continue;

        root->l = bT(ml, idx - 1, pl + 1, pl + lLen);
        root->r = bT(idx + 1, mr, pr - rLen + 1, pr);

        root->s = (root->l ? (root->l->v + root->l->s) : 0) +
                  (root->r ? (root->r->v + root->r->s) : 0);

        break;
    }

    return root;
}

int main() {
    mo = splitCin(' ');
    po = splitCin(' ');

    int n = mo.size();

    for (int i = 0; i < n; i++) {
        mi[mo[i]].emplace_back(i);
    }

    // 根据中序序列和前序序列还原树结构
    Nod *root = bT(0, n - 1, 0, n - 1);

    // 中序遍历
    in(root);

    return 0;
}

python

class Node:
    def __init__(self, val):
        self.v = val  # 当前节点的值
        self.s = 0    # 当前节点的左子树+右子树的和
        self.l = None # 左子节点
        self.r = None # 右子节点

def split_input(sep):
    return list(map(int, input().strip().split(sep)))

def inorder_traversal(root):
    if not root:
        return
    inorder_traversal(root.l)
    print(root.s, end=' ')
    inorder_traversal(root.r)

def count(nums, l, r):
    c = {}
    for i in range(l, r):
        c[nums[i]] = c.get(nums[i], 0) + 1
    return c

def neq(ml, pl, sz, mo, po):
    c1 = count(mo, ml, ml + sz)
    c2 = count(po, pl, pl + sz)

    if len(c1) != len(c2):
        return True

    for key in c1:
        if c1[key] != c2.get(key, 0):
            return True

    return False

def build_tree(ml, mr, pl, pr, mo, po, mi):
    if pl > pr:
        return None

    root_val = po[pl]
    root = Node(root_val)

    for idx in mi[root_val]:
        if idx < ml or idx > mr:
            continue

        l_len = idx - ml
        if neq(ml, pl + 1, l_len, mo, po):
            continue

        r_len = mr - idx
        if neq(idx + 1, pr - r_len + 1, r_len, mo, po):
            continue

        root.l = build_tree(ml, idx - 1, pl + 1, pl + l_len, mo, po, mi)
        root.r = build_tree(idx + 1, mr, pr - r_len + 1, pr, mo, po, mi)

        root.s = (root.l.v + root.l.s if root.l else 0) + (root.r.v + root.r.s if root.r else 0)
        break

    return root

def main():
    mo = split_input(' ')
    po = split_input(' ')
    
    n = len(mo)

    # 记录中序遍历序列中，序列元素值所在位置
    mi = {}
    for i in range(n):
        if mo[i] not in mi:
            mi[mo[i]] = []
        mi[mo[i]].append(i)

    # 根据中序序列和前序序列还原树结构
    root = build_tree(0, n - 1, 0, n - 1, mo, po, mi)

    # 中序遍历
    inorder_traversal(root)

if __name__ == "__main__":
    main()

java

import java.util.*;

class Node {
    int v; // 当前节点的值
    int s; // 当前节点的左子树 + 右子树的和
    Node l; // 左子节点
    Node r; // 右子节点

    Node(int val) {
        this.v = val;
        this.s = 0;
        this.l = null;
        this.r = null;
    }
}

public class Main {
    // 中序遍历序列
    static List<Integer> mo;
    // 前序遍历序列
    static List<Integer> po;
    // 记录中序遍历序列中，序列元素值所在位置
    static Map<Integer, List<Integer>> mi;

    // 输入解析函数
    public static List<Integer> splitCin(String input) {
        String[] tokens = input.split(" ");
        List<Integer> nums = new ArrayList<>();
        for (String token : tokens) {
            nums.add(Integer.parseInt(token));
        }
        return nums;
    }

    // 中序遍历
    public static void in(Node root) {
        if (root == null) return;
        in(root.l);
        System.out.print(root.s + " ");
        in(root.r);
    }

    // 统计 nums 的 [l, r) 区间内各个元素出现次数
    public static Map<Integer, Integer> count(List<Integer> nums, int l, int r) {
        Map<Integer, Integer> c = new HashMap<>();
        for (int i = l; i < r; i++) {
            c.put(nums.get(i), c.getOrDefault(nums.get(i), 0) + 1);
        }
        return c;
    }

    // 判断两个 map 是否相同
    public static boolean neq(int ml, int pl, int sz) {
        Map<Integer, Integer> c1 = count(mo, ml, ml + sz);
        Map<Integer, Integer> c2 = count(po, pl, pl + sz);

        if (c1.size() != c2.size()) return true;

        for (Map.Entry<Integer, Integer> entry : c1.entrySet()) {
            if (!c2.getOrDefault(entry.getKey(), 0).equals(entry.getValue())) return true;
        }

        return false;
    }

    // 根据中序遍历序列、前序遍历序列还原树结构
    public static Node bT(int ml, int mr, int pl, int pr) {
        if (pl > pr) return null;

        int rootVal = po.get(pl);
        Node root = new Node(rootVal);

        for (int idx : mi.get(rootVal)) {
            if (idx < ml || idx > mr) continue;

            int lLen = idx - ml;
            if (neq(ml, pl + 1, lLen)) continue;

            int rLen = mr - idx;
            if (neq(idx + 1, pr - rLen + 1, rLen)) continue;

            root.l = bT(ml, idx - 1, pl + 1, pl + lLen);
            root.r = bT(idx + 1, mr, pr - rLen + 1, pr);

            root.s = (root.l != null ? (root.l.v + root.l.s) : 0) +
                      (root.r != null ? (root.r.v + root.r.s) : 0);
            break;
        }

        return root;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        mo = splitCin(scanner.nextLine());
        po = splitCin(scanner.nextLine());

        int n = mo.size();
        mi = new HashMap<>();

        for (int i = 0; i < n; i++) {
            mi.putIfAbsent(mo.get(i), new ArrayList<>());
            mi.get(mo.get(i)).add(i);
        }

        // 根据中序序列和前序序列还原树结构
        Node root = bT(0, n - 1, 0, n - 1);

        // 中序遍历
        in(root);
        scanner.close();
    }
}

题目内容

给出一个二叉树如下图所示：

请由该二叉树生成一个新的二叉树，它满足其树中的每个节点将包含原始树中的左子树和右子树的和。

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

输入描述

2行整数，第1行表示二叉树的中序遍历，第2行表示二叉树的前序遍历，以空格分割

例如：

7 -2 6 6 9

6 7 -2 9 6

输出描述

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

例如：

-2 0 20 0 6

样例1

输入

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

输出

0 3 0 7 0 2 0