首页 > 试题广场 >

将满二叉树转换为求和树

[编程题]将满二叉树转换为求和树
  • 热度指数：13699 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出满二叉树的前序遍历结果和中序遍历结果，编写算法将其转化为求和树

什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。

二叉树：

求和树：


二叉树给出前序和中序输入，求和树要求中序输出；
所有处理数据不会大于int；

数据范围：二叉树的节点数满足 ,节点上的值满足

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


输出描述:
1行整数，表示求和树的中序遍历，以空格分割
示例1

输入

10 -2 8 -4 6 7 5
8 -2 -4 10 7 6 5

输出

0 4 0 20 0 12 0
算法知识视频讲解
开通博客
头像 ls.joshua
发表于 2020-04-04 14:14:31
#include<bits/stdc++.h> using namespace std; void createTree(const vector<int> &arr, int pleft, int pright, int vleft, int vright, ve 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 laglangyue
发表于 2020-05-21 21:19:08
满二叉树，中序遍历就能还原二叉树，这算是本题的bug。中序二叉满树到中序求和二叉树参考归并排序的写法。 import java.lang.reflect.Array; import java.util.Arrays; import java.util.Scanner; public class 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 右神
发表于 2022-08-14 23:29:09
分治思想 import java.util.*; public class Main{     static int[] res;     public  展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 yorkchen
发表于 2020-04-04 21:45:28
class TreeNode:     def __init__(self,val):         self.val = val &nb 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 勇敢牛牛，不怕困难！
发表于 2022-01-13 18:23:04
大模拟的解法，感觉没有必要 #include <iostream> #include <cstring> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *ri 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 贪吃的迪恩顶呱呱
发表于 2024-05-07 22:47:46
根据前序遍历，在中序遍历中找到树的根，递归计算左右子树的和 #include <iostream> #include <vector> using namespace std; void calSum(vector<int>& preorder, vec 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客499819205号
发表于 2021-12-15 15:14:01
#include<iostream> #include<vector> using namespace std; struct TreeNode {     int val;  &nbs 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 秋風掃落葉
发表于 2019-09-17 15:00:13
import java.util.*; public class SumTree { static int[] preOrder; static int[] inOrder; static List<Integer> inOrderRes; public static void mai 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 我不打朋友圈
发表于 2021-12-16 14:38:31
import java.util.; import java.io.; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader in = new BufferedReade 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 秋風掃落葉
发表于 2019-09-16 17:22:13
import java.util.Scanner;/*主要是对于二叉树前序遍历和中序遍历关系转换的理解，对于每个求和节点脑海中需要构想出空间位置关系*/class Main{ static void main(String[] args){ Scanner sc = new S 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 快手 模拟 2019 Java工程师 递归
上传者：小小
难度：
64条回答 13591浏览

热门推荐

通过挑战的用户

查看代码

相关试题

将满二叉树转换为求和树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号