什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。
二叉树：
求和树：
二叉树给出前序和中序输入，求和树要求中序输出；
所有处理数据不会大于int；
数据范围：二叉树的节点数满足 
,节点上的值满足 
[编程题]将满二叉树转换为求和树
- 热度指数：13636 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
给出满二叉树的前序遍历结果和中序遍历结果，编写算法将其转化为求和树
什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。
二叉树：
求和树：
什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。
二叉树：
求和树：
输入描述:
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
"""
本题有如下规律：
求和树的根节点 = 除本身外原二叉树所有子节点之和，
本题中根节点为中序遍历数组中正中间项（满二叉树）
递归求得左右子树，直到子树节点个数为1返回[0]。
需要考虑根节点在两侧的情况，树节点个数为0时，返回空[]
"""
def func(d):
if len(d) == 1: return [0]
elif len(d) == 0: return []
mid = len(d) // 2 # 满二叉树根节点即正中间数值，前序遍历数组本题中用不到，可删除
return func(d[:mid]) + [sum(d[:]) - d[mid]] + func(d[mid + 1:])
if __name__ == "__main__":
a = list(map(int, input().strip().split()))
d = list(map(int, input().strip().split()))
ans = func(d)
print(' '.join(map(str, ans)))
未考虑满二叉树这一性质，求解如下：
"""
本题有如下规律：
求和树的根节点 = 除本身外所有子节点之和，
递归求得左右子树，直到子树节点个数为1返回[0]。
需要考虑根节点在两侧的情况，树节点个数为0时，返回空[]
"""
import sys
def func(a, d):
if len(a) == 1:
return [0]
elif len(a) == 0:
return []
mid = d.index(a[0])
d[mid] = sum(d[:]) - d[mid]
return func(a[1:(mid + 1)], d[:mid]) + \
[sum(d[:]) - d[mid]] + \
func(a[(mid + 1):], d[mid + 1:])
if __name__ == "__main__":
# sys.stdin = open('input.txt', 'r')
a = list(map(int, input().strip().split()))
d = list(map(int, input().strip().split()))
ans = func(a, d)
print(' '.join(map(str, ans)))
编辑于 2019-07-04 12:34:29
回复(9)
/*
关键思路：二叉树加一个sum属性。
根据先序中序的序列，构建二叉树。
利用后序遍历来更新节点sum值。
最后通过中序遍历得到答案序列。
估计有更好的方法。
希望同学们有更巧妙的办法后叫我一下。
*/
import java.util.*;
class STNode {
int val;
int sum;
STNode left = null;
STNode right = null;
public STNode(int val) {
this.val = val;
}
}
public class Main {
static int[] preOrder;
static int[] inOrder;
static List<Integer> ans; //存和的中序遍历。
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s1 = in.nextLine();
String s2 = in.nextLine();
String[] str1 = s1.split(" ");
String[] str2 = s2.split(" ");
int len = str1.length;
preOrder = new int[len];
inOrder = new int[len];
for (int i = 0; i < len; i++) {
preOrder[i] = Integer.parseInt(str1[i]);
}
for (int i = 0; i < len; i++) {
inOrder[i] = Integer.parseInt(str2[i]);
}
STNode sroot = creatTree(0, 0, len - 1);
sumNode(sroot);
ans = new ArrayList<>();
inOrderGo(sroot);
for (int i : ans) {
System.out.print(i + " ");
}
System.out.println();
}
//根据先序和中序遍历构建二叉树。
static STNode creatTree(int root, int beg, int end) {
if (beg > end) return null;
STNode node = new STNode(preOrder[root]);
int loc = 0;
int cnt = 0;
for (loc = beg; loc <= end; loc++) {
cnt++;
if (preOrder[root] == inOrder[loc])
break;
}
node.left = creatTree(root + 1, beg, loc - 1);
node.right = creatTree(root + cnt, loc + 1, end);
return node;
}
//更新sum值。
static void sumNode(STNode node) {
if (node.left == null && node.right == null) {
node.sum = 0;
} else if (node.left == null) {
sumNode(node.right);
node.sum = node.right.sum + node.right.val;
} else if (node.right == null) {
sumNode(node.left);
node.sum = node.left.sum + node.left.val;
} else {
sumNode(node.left);
sumNode(node.right);
node.sum = node.left.sum + node.left.val + node.right.sum + node.right.val;
}
}
//中序遍历。
static void inOrderGo(STNode node) {
if (node == null) return;
inOrderGo(node.left);
ans.add(node.sum);
inOrderGo(node.right);
}
}
编辑于 2019-06-27 21:12:05
回复(5)
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
sc.nextLine();//满二叉树应该只需要中序遍历就可以确定唯一的树，所以不保存第一行输入
String zhong = sc.nextLine();
String[] split = zhong.split(" ");
int[] a = new int[split.length];//中序遍历保存到数组a中
for(int i=0;i<a.length;i++) {
a[i] = Integer.parseInt(split[i]);
}
int[] ans = new int[a.length];//保存中序遍历的输出结果
fun(a,0,a.length-1,ans);
for(int i:ans){
System.out.print(i+" ");
}
sc.close();
}
private static int fun(int[] a,int left,int right,int[] ans) {
int mid = (right+left)/2;//中间元素不参与这一轮的计算
if(right-left==2) {//出口条件
ans[mid] = a[right] + a[left];
ans[left] = 0;
ans[right] = 0;
return a[mid]+ans[mid];
}else {
ans[mid] = fun(a,left,mid-1,ans) + fun(a,mid+1,right,ans);
return a[mid]+ans[mid];
}
}
}
发表于 2019-10-11 16:18:48
回复(0)
//重构二叉树做法
import java.util.*;
class TreeNode{int val=0;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
public class Main{
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
String[] temp = sc.nextLine().split(" ");
//先序数组
int[] pre = new int[temp.length];
for (int i = 0; i < pre.length; i++) {pre[i] = Integer.parseInt(temp[i]);
}
temp = sc.nextLine().split(" ");
//中序数组
int[] mid = new int[temp.length];
for (int j = 0; j < mid.length; j++) {mid[j] = Integer.parseInt(temp[j]);
}
//二叉树的根结点
TreeNode root = arrToTree(pre, 0, pre.length - 1, mid, 0, mid.length - 1); //求各个结点的和
func(root);
//中序输出结果
midOut(root); }
//数组 转成二叉树
public static TreeNode arrToTree(int []pre,int ps,int pe,int []mid,int ms,int me){if(ps>pe||ms>me){
return null;
}
TreeNode node=new TreeNode(pre[ps]);
for(int i=ms;i<=me;i++){
if(mid[i]==node.val){
int len=i-ms;
node.left=arrToTree(pre,ps+1,ps+len,mid,ms,i-1);
node.right=arrToTree(pre,ps+len+1,pe,mid,i+1,me);
break;
}
}
return node;
}
//求结点的和 结点的和等于该结点的左、右结点的val+func(左结点)+func(右结点)
public static int func(TreeNode node){
if(node==null) return 0;
int left=0;
int right=0;
if(node.left!=null) left=node.left.val;
if(node.right!=null) right=node.right.val;
node.val=left+right+func(node.left)+func(node.right);
return node.val;
}
//中序输出
public static void midOut(TreeNode root){if(root.left!=null){
midOut(root.left);
}
System.out.print(root.val+" ");
if(root.right!=null){
midOut(root.right);
}
}
}
发表于 2019-09-12 15:27:03
回复(0)
Python版本。利用输入的中序遍历结果和先序遍历结果获得每个结点的求和。
class TreeNode:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
class Solution:
def createTree(self,preOrder,midOrder):
if len(preOrder) ==0 :
return None
root_index = midOrder.index(preOrder[0])
if len(preOrder) == 1:
root = TreeNode(0)
else:
root = TreeNode(sum(preOrder[1:]))
left_pre = preOrder[1:root_index+1]
right_pre = preOrder[root_index+1:]
left_mid = midOrder[0:root_index]
right_mid = midOrder[root_index+1:]
root.left = self.createTree(left_pre,left_mid)
root.right = self.createTree(right_pre,right_mid)
return root
def midTreverse(self,root):
if root == None:
return []
return self.midTreverse(root.left) + [root.val] + self.midTreverse(root.right)
s = Solution()
preOrder = [int(x) for x in input().split()]
midOrder = [int(x) for x in input().split()]
root = s.createTree(preOrder,midOrder)
print(" ".join(list(map(str,s.midTreverse(root)))))
发表于 2019-08-21 18:23:26
回复(0)
//只通过60%，没有考虑到节点重复的情况
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String s1=sc.nextLine();
String s2=sc.nextLine();
String[] str1=s1.split(" ");
String[] str2=s2.split(" ");
int[] preorder=new int[str1.length];
int[] inorder=new int[str2.length];
int n=preorder.length;
for(int i=0;i<preorder.length;i++){
preorder[i]=Integer.parseInt(str1[i]);
inorder[i]=Integer.parseInt(str2[i]);
}
func(preorder,0,n-1,inorder,0,n-1);
for(int i=0;i<n;i++){
System.out.print(inorder[i]);
if(i!=n-1){
System.out.print(" ");
}
}
}
public static void func(int[] preorder,int ps,int pl,int[] inorder,int is,int il){
if(ps==pl){
inorder[is]=0;
return;
}
int rootVal=preorder[ps];
int im=is;
while(im<=il && inorder[im]!=rootVal){
im++;
}
inorder[im]=sum(inorder,is,im-1)+sum(inorder,im+1,il);
func(preorder,ps+1,ps+im-is,inorder,is,im-1);
func(preorder,ps+im-is+1,pl,inorder,im+1,il);
}
public static int sum(int[] inorder,int s,int l){
int sum=0;
for(int i=s;i<=l;i++){
sum+=inorder[i];
}
return sum;
}
}
发表于 2019-08-05 19:44:25
回复(2)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
const int BUFFER_SIZE = 1024;
const char* const DELIM = " ";
typedef int ElemType;
// The definition of Binary Tree Node
typedef struct TreeNode {
ElemType data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode, *PTreeNode;
// =================== The begin of function declaration ====================
// 将普通的二叉树转换为求和树
int convertToSumTree(PTreeNode root);
// 把二叉树节点的数据成员打印在公屏上
void printTreeNodeData(PTreeNode node);
// 中序遍历二叉树
void inorderTraversal(PTreeNode root, void (*visit) (PTreeNode));
// 根据二叉树的先序（前序）和中序遍历序列构造二叉树本体
PTreeNode constructTree(const int* preorder, const int* inorder, int i, int j, int n);
// debug helper function
void __printArray(int* arr, const int size);
// =================== The end of function declaration ====================
int main(const int argc, const char* argv[]) {
char pre_str[1 << 10] = { 0 }, in_str[1 << 10] = { 0 };
fgets(pre_str, BUFFER_SIZE, stdin);
fgets(in_str, BUFFER_SIZE, stdin);
int preorder[1024], inorder[1024],
preorderSize = 0, inorderSize = 0;
char* tok = strtok(pre_str, DELIM);
while (tok) {
*(preorder + preorderSize++) = atoi(tok);
tok = strtok(NULL, DELIM);
}
tok = strtok(in_str, DELIM);
while (tok) {
*(inorder + inorderSize++) = atoi(tok);
tok = strtok(NULL, DELIM);
}
PTreeNode root = constructTree(preorder, inorder, 0, 0, preorderSize);
convertToSumTree(root); // 将普通的二叉树转换为求和树
return inorderTraversal(root, printTreeNodeData), 0;
}
int convertToSumTree(PTreeNode root) {
if (!root) return 0;
const int left = convertToSumTree(root->left);
const int right = convertToSumTree(root->right);
const int sum = root->data + left + right;
root->data = left + right;
return sum;
}
PTreeNode constructTree(const int* preorder, const int* inorder, int i, int j, int n) {
if (n <= 0) return NULL;
PTreeNode root = (PTreeNode) malloc(sizeof(TreeNode));
if (!root) {
fprintf(stderr, "constructTree memory overflow: %s\n", strerror(errno));
return NULL;
}
(*root).data = *(preorder + i);
(*root).left = (*root).right = NULL;
if (n == 1) return root;
int k = j;
while (*(inorder + k) != *(preorder + i)) ++k;
int l = k - j;
root->left = constructTree(preorder, inorder, i + 1, j, l);
root->right = constructTree(preorder, inorder, i + 1 + l, k + 1, n - 1 - l);
return root;
}
void printTreeNodeData(PTreeNode node) {
fprintf(stdout, "%d ", (*node).data);
}
void inorderTraversal(PTreeNode root, void (*visit) (PTreeNode)) {
if (!root) return;
inorderTraversal((*root).left, visit);
visit(root);
inorderTraversal((*root).right, visit);
}
void __printArray(int* arr, const int size) {
int i;
for (i = 0; i < size; ++i) {
fprintf(stdout, "%2d", *(arr + i));
if (i < size - 1) fputc(32, stdout);
}
fputc(10, stdout);
}
发表于 2021-07-13 10:58:44
回复(0)
输入的先序遍历序列没有用，直接用递归对中序遍历序列进行求和操作。遇到叶子节点返回0，否则分别构建左右的求和树序列，并将本结点的和放在中间。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br.readLine(); // 忽略先序遍历
String[] strArr = br.readLine().trim().split(" ");
ArrayList<Integer> inOrder = new ArrayList<>();;
for(int i = 0; i < strArr.length; i++) inOrder.add(Integer.parseInt(strArr[i]));
ArrayList<Integer> res = sumTree(inOrder);
for(int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
System.out.println();
}
private static ArrayList<Integer> sumTree(ArrayList<Integer> seq) {
// 到达叶子节点就返回0
if(seq.size() == 1){
ArrayList<Integer> temp = new ArrayList<>();
temp.add(0);
return temp;
}
// 本子树的根节点
int root = seq.size() / 2;
int sum = 0; // 初始化本结点的左右子树和
// 左子树序列
ArrayList<Integer> leftTree = new ArrayList<>();
for(int i = 0; i < root; i++) {
leftTree.add(seq.get(i));
sum += seq.get(i);
}
// 对左子树进行求和操作
leftTree = sumTree(leftTree);
// 右子树序列
ArrayList<Integer> rightTree = new ArrayList<>();
for(int i = root + 1; i < seq.size(); i++) {
rightTree.add(seq.get(i));
sum += seq.get(i);
}
// 对右子树进行求和操作
rightTree = sumTree(rightTree);
leftTree.add(sum);
leftTree.addAll(rightTree);
return leftTree;
}
}
编辑于 2021-02-20 22:52:12
回复(0)
/*等成绩ing,希望我上岸- -。*/
#include <bits/stdc++.h>
using namespace std;
const int AX = 1e5 + 666 ;
char s[AX] ;
vector<int>pre_v , in_v ;
int sum[AX] ;
struct TreeNode{
int val ;
int sum ;
TreeNode *l ;
TreeNode *r ;
TreeNode( int val ) : val(val) , sum(0) , l(NULL), r(NULL) {}
};
void input(){
fgets( s , AX , stdin );
char *p = strtok( s , " " ) ;
while( p ){
pre_v.push_back(atoi(p));
p = strtok( NULL , " " );
}
fgets( s , AX , stdin );
p = strtok( s , " " ) ;
while( p ){
in_v.push_back(atoi(p));
p = strtok( NULL , " " );
}
}
TreeNode* build( vector<int>pre , vector<int>in ){
if( !pre.size() || !in.size() ){
return NULL ;
}
TreeNode* rt = new TreeNode(pre[0]);
for( int i = 0 ; i < in.size() ; i++ ){
if( in[i] == pre[0] ){
vector<int>p1( pre.begin() + 1 , pre.begin() + i + 1 );
vector<int>v1( in.begin() , in.begin() + i ) ;
rt->l = build( p1 , v1 );
vector<int>p2( pre.begin() + i + 1 , pre.end() );
vector<int>v2( in.begin() + i + 1 , in.end() ) ;
rt->r = build( p2 , v2 );
break ;
}
}
return rt ;
}
int dfs( TreeNode *rt ){
if( rt == NULL ) return 0 ;
int ans = 0 ;
if( rt -> l ) ans += dfs( rt -> l );
if( rt -> r ) ans += dfs( rt -> r );
rt -> sum = ans ;
return ans + rt -> val ;
}
void in_order(TreeNode* rt){
if( rt -> l ) in_order( rt -> l );
cout << rt -> sum << ' ' ;
if( rt -> r ) in_order( rt -> r );
}
int main(){
input();
TreeNode* root = build( pre_v , in_v ) ;
dfs( root );
int len = in_v.size() ;
in_order(root);
return 0 ;
}
编辑于 2020-02-21 14:31:45
回复(0)
#include <iostream>
#include <vector>
using namespace std;
vector<int> t1;
vector<int> t2;
vector<int>* res;
int main() {
int sumTree(int l, int r);
int i = 0;
char c = ' ';
vector<int>* t = &t1;
while (cin) {
cin >> noskipws >> i >> c;
t->push_back(i);
if (c == '\n') {
if (t != &t2)
t = &t2;
else
break;
}
}
res = new vector<int>((t1.size()));
sumTree(0, t1.size() - 1);
for (int i = 0; i < res->size(); i++) {
cout << (*res)[i];
if (i + 1 != res->size()) {
cout << ' ';
}
else {
cout << endl;
}
}
return 0;
}
int curNode = 0;
int sumTree(int l,int r) {
int sum = 0;
if (l >= r) {
if (curNode >= t1.size())
return 0;
return t1[curNode];
}
int curV = t1[curNode];
int pos = 0;
for (int i = l; i <= r; i++) {
if (t2[i] == t1[curNode]) {
pos = i;
break;
}
}
curNode++;
sum += sumTree(l, pos-1);
curNode++;
sum += sumTree(pos + 1, r);
int resPos = (l + r) / 2;
if ((l + r) % 2)
resPos++;
(*res)[resPos] = sum;
sum += curV;
return sum;
} 写完才发现是满二叉树，我枯了
编辑于 2019-09-27 18:31:52
回复(0)
用了最笨的还原二叉树的方法，才发现有更简单的方法，就当作是练习吧
import java.util.*;
class TreeNode{
int val;
TreeNode left = null;
TreeNode right = null;
TreeNode(int val) {this.val = val;}
}
public class Main{
public static void main(String []args){
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()){
String[] str1 = sc.nextLine().split(" ");
String[] str2 = sc.nextLine().split(" ");
int[] pre = new int[str1.length];
int[] in = new int[str2.length];
for (int i=0;i<pre.length;i++){
pre[i] = Integer.valueOf(str1[i]);
in[i] = Integer.valueOf(str2[i]);
}
TreeNode root = reCon(pre, in);
root = SumTree(root);
InOrderPrint(root);
}
}
public static void InOrderPrint(TreeNode root){
if (root == null) return;
InOrderPrint(root.left);
System.out.print(root.val+" ");
InOrderPrint(root.right);
}
public static TreeNode reCon(int[] pre, int[] in){
if (pre.length == 0) return null;
TreeNode root = new TreeNode(pre[0]);
for (int i=0;i<in.length;i++)
if (in[i] == pre[0]){
root.left = reCon(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
root.right = reCon(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
}
return root;
}
public static TreeNode SumTree(TreeNode root){
if (root == null) return root;
TreeNode newroot = new TreeNode(Sum(root)-root.val);
newroot.left = SumTree(root.left);
newroot.right = SumTree(root.right);
return newroot;
}
public static int Sum(TreeNode root){
if (root == null) return 0;
return root.val+Sum(root.left)+Sum(root.right);
}
}
发表于 2019-09-24 02:08:28
回复(0)
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int tree[N], res[N], mark[N];
vector<int> foo, bar;
void read(vector<int> &vec){
int num = 0, sg = 1;
char c;
while((c = getchar()) != '\n'){
if(c != ' '){
if(c != '-'){
num = num * 10 + (c - '0');
} else {
sg = -1;
}
} else {
vec.push_back(num * sg);
num = 0;
sg = 1;
}
}
vec.push_back(num * sg);
}
void ask(int index, int lf, int rf, int lb, int rb){
if(lf > rf || lb > rb){
return;
}
int llen, need;
tree[index] = foo[lf];
mark[index] = 0;
for (int i = lb; i <= rb; i++){
if(bar[i] == foo[lf]){
need = i;
break;
}
}
llen = need - lb;
ask(index * 2, lf + 1, lf + llen, lb, rb + llen - 1);
ask(index * 2 + 1, lf + llen + 1, rf, need + 1, rb);
}
void print(int index){
if(mark[index] == -1){
return;
}
print(index * 2);
cout << res[index] << " ";
print(index * 2 + 1);
}
int main(){
read(foo);
read(bar);
memset(mark, -1, sizeof(mark));
int len, depth;
len = foo.size() - 1;
depth = (int)log2(len + 1) + 1;
ask(1, 0, len, 0, len);
for (int i = depth; i >= 1; i--){
int start = (1 << i);
for (int j = 0, k = start; j < start / 2; j++, k += 2){
res[k / 2] = res[k] + res[k + 1];
if(mark[k] != -1){
res[k / 2] += tree[k];
}
if(mark[k + 1] != -1){
res[k / 2] += tree[k + 1];
}
}
}
print(1);
return 0;
}
发表于 2019-09-06 11:02:28
回复(0)
#include <bits/stdc++.h>
using namespace std;
void DFS(vector<int> pre, vector<int> in, int p, int l, int r, vector<int> &v){
if(l>r)
return;
else if(l==r)
v[l] = 0;
else{
int s = 0;
for(int i=l;i<=r;i++)
s += in[i];
int k = l;
for(;k<=r;k++){
if(in[k] == pre[p]){
break;
}
}
s -= in[k];
v[k] = s;
DFS(pre, in, p+1, l, k-1, v);
DFS(pre, in, p+k-l+1, k+1, r, v);
}
}
int main(){
string s, x;
getline(cin, s);
vector<int> pre;
vector<int> in;
istringstream ss(s);
while(ss>>x)
pre.push_back(stoi(x));
getline(cin, s);
istringstream ss1(s);
while(ss1>>x)
in.push_back(stoi(x));
int n = pre.size();
vector<int> v(n, 0);
DFS(pre, in, 0, 0, n-1, v);
for(int i=0;i<n;i++)
cout<<v[i]<<" ";
return 0;
}
发表于 2019-08-06 13:54:17
回复(0)
虽然过了，但感觉只适用于没有重复节点的情况，贴出来给大家查看一下，思路不难就是利用二叉树的特性进行标记再求和！
import java.util.Scanner;
public class Main {
private static int getIdx(String[] nums, String target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i].equals(target)) return i;
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String preOrder = sc.nextLine();
String inOrder = sc.nextLine();
String[] preNumbers = preOrder.split(" ");
String[] inNumbers = inOrder.split(" ");
int n = inNumbers.length;
int[] ans = new int[n];
boolean[] used = new boolean[n];
for (String preNumber : preNumbers) {
int idx = getIdx(inNumbers, preNumber);
int i = idx - 1;
while (i >= 0 && !used[i]) {
ans[idx] += Integer.valueOf(inNumbers[i--]);
}
int j = idx + 1;
while (j < n && !used[j]) {
ans[idx] += Integer.valueOf(inNumbers[j++]);
}
used[idx] = true;
}
for (int i = 0; i < n; i++) {
System.out.print(ans[i]);
if (i != n - 1) System.out.print(' ');
}
}
}
}
发表于 2019-07-24 13:36:28
回复(0)
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include <numeric>
using namespace std;
void sumtree(vector<int> &inorder, int left, int right){
int mid = (left + right)/2;
if(mid == left){
inorder[mid] = 0;
return;
}
inorder[mid] = accumulate(inorder.begin()+left, inorder.begin()+right, -inorder[mid]);
sumtree(inorder, left, mid);
sumtree(inorder, mid+1, right);
}
int main(void){
string line;
getline(cin, line);
istringstream pre_stream(line);
vector<int> preorder((istream_iterator<int>(pre_stream)), istream_iterator<int>());
getline(cin, line);
istringstream in_stream(line);
vector<int> inorder((istream_iterator<int>(in_stream)), istream_iterator<int>());
sumtree(inorder, 0, inorder.size());
copy(inorder.begin(), inorder.end(),ostream_iterator<int>(cout, " "));
cout<<endl;
return 0;
} 因为是满二叉树，其实结果跟前序遍历数组无关，只和中序遍历数组有关，并且中序数组一定是奇数个，结果索引为偶数的一定为0，索引为奇数的值是中序遍历数组其他值之和(不包括自己)，使用二分法找到根节点，然后计算子树之和，不用还原二叉树。
编辑于 2019-08-16 21:20:41
回复(7)
看过大神的详解之后， 豁然开朗， 题目中所给的前序遍历只是用来迷惑我们的，因为满二叉树只需要中序遍历 即可退出二叉树形状，但是不用构建，只需要用二分法理清每个节点之间的关系，利用递归即可求解。
// 核心方法
public Integer help(int [] nums,int low,int high) {
if(low == high) {
int tmp = nums[low];
nums[low] = 0;
return tmp;
}
int sum = 0;
int mid = (low+high)/2;
sum += help(nums,low,mid-1); //用记录左右孩子的和
sum += help(nums,mid+1,high);
int tmp = nums[mid];
nums[mid] = sum;
return sum + tmp; // 返回原来的值和新的值
}
发表于 2020-02-14 16:19:50
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
List<Integer> list = new ArrayList<>();
while(sc.hasNext()){
list.add(sc.nextInt());
}
int[] preOrder = new int[list.size()/2];
int[] inOrder = new int[list.size()/2];
for(int i=0;i<list.size();i++){
if(i < list.size()/2)
preOrder[i] = list.get(i);
else
inOrder[i-list.size()/2] = list.get(i);
}
TreeNode root = createTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
dfs(root);
}
//中序遍历输出结果
public static void dfs(TreeNode root){
if(root == null)
return;
dfs(root.left);
int num = PrintNode(root);
System.out.print(num + " ");
dfs(root.right);
}
//打印节点
public static int PrintNode(TreeNode root){
if(root == null)
return 0;
int Left = 0,Right = 0;
if(root.left != null)
Left = root.left.val;
if(root.right != null)
Right = root.right.val;
return Left + Right + PrintNode(root.left) + PrintNode(root.right);
}
//建树
public static TreeNode createTree(int[] preOrder,int preStart,int preEnd,int[] inOrder,int inStart,int inEnd){
if(preStart > preEnd || inStart > inEnd)
return null;
int target = preOrder[preStart];
TreeNode root = new TreeNode(target);
int index;
for(index=inStart;index<=inEnd;index++)
if(inOrder[index] == target)
break;
int leftLength = index-inStart;
root.left = createTree(preOrder,preStart+1,preStart+leftLength,inOrder,inStart,index-1);
root.right = createTree(preOrder,preStart+leftLength+1,preEnd,inOrder,index+1,inEnd);
return root;
}
}
//构造树
class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x){val = x;}
}
发表于 2020-05-31 11:00:34
回复(0)
唉，一个超长的代码，建树用的是代码随想录的方法，求和树用的是题解里面的
#include <iostream>
#include <memory>
#include <sys/types.h>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode():val(0),left(nullptr),right(nullptr){};
TreeNode(int x):val(x),left(nullptr),right(nullptr){};
};
TreeNode* buildTree(vector<int>&preOrder,vector<int>&inOrder){
if(preOrder.size()==0) return nullptr;
int root_val=preOrder[0];
TreeNode* root=new TreeNode(root_val);
int mid_idx=0;
for(int i=0;i<inOrder.size();i++){
if(inOrder[i]==root_val)
mid_idx=i;
}
vector<int>leftinOrder(inOrder.begin(),inOrder.begin()+mid_idx);
vector<int>rightinOrder(inOrder.begin()+mid_idx+1,inOrder.end());
vector<int>leftpreOrder(preOrder.begin()+1,preOrder.begin()+leftinOrder.size()+1);
vector<int>rightpreOrder(preOrder.begin()+leftinOrder.size()+1,preOrder.end());
root->left=buildTree(leftpreOrder,leftinOrder);
root->right=buildTree(rightpreOrder,rightinOrder);
return root;
}
int dfs(TreeNode* node){
if(node==nullptr) return 0;
int sum=0;
sum+=dfs(node->left);
sum+=dfs(node->right);
int temp=node->val+sum;
node->val=sum;
return temp;
}
void myprint(TreeNode* node){
if(node==nullptr) return;
myprint(node->left);
cout<<node->val<<" ";
myprint(node->right);
}
int main() {
vector<int>preOrder,inOrder;
int x;
while(cin>>x){
preOrder.push_back(x);
if(cin.get()=='\n') break;
}
while(cin>>x){
inOrder.push_back(x);
if(cin.get()=='\n') break;
}
if(preOrder.size()==0||inOrder.size()==0) return 0;
TreeNode* root=buildTree(preOrder,inOrder);
dfs(root);
myprint(root);
}
发表于 2023-04-10 21:04:36
回复(0)
// 只在中序遍历上操作
#include <iostream>
#include <vector>
using namespace std;
int add(vector<int> &tree, int rangeLeft, int rangeRight)
{
if(rangeLeft>rangeRight){ return 0;}
int center = (rangeLeft+rangeRight)/2;
int centerVal = tree[center];
int left = add(tree, rangeLeft, center-1);
int right = add(tree, center+1, rangeRight);
tree[center] = left+right;
return left + right + centerVal;
}
int main() {
vector<int> first;
int input;
while(cin >> input)
{
first.push_back(input);
}
vector<int> mid(first.begin()+(first.size()/2), first.end());
add(mid, 0, mid.size()-1);
for(int i=0; i<mid.size(); i++)
{
cout << mid[i] << " ";
}
}
发表于 2022-11-03 16:02:00
回复(0)
#include<bits/stdc++.h>
using namespace std;
void help(vector<int>& tree,int l,int r)
{
if(l==r)
tree[l]=0;
int m=(l+r)/2;
tree[m]=0;
for(int i=l;i<=r;i++)
{
if(i!=m)
tree[m]+=tree[i];
}
}
void help1(vector<int>& tree,int l,int r)
{
if(l>r)
return;
int m=(l+r)/2;
help(tree,l,r);
help1(tree,l,m-1);
help1(tree,m+1,r);
}
int main()
{
vector<int> tree;
int a;
while(cin>>a)
{
tree.push_back(a);
}
int n=tree.size();
vector<int> t(tree.begin()+n/2,tree.end());
int l=0,r=t.size()-1;
help1(t,l,r);
for(auto it:t)
cout<<it<<" ";
return 0;
}
仅利用中序遍历即可得出最终答案，在满二叉树中，根节点是中间节点，把根节点左右两边的值 加起来就是根节点的结果，然后利用递归求根节点的左右节点的值，其中help1函数是为了确定节 点计算的范围，help函数是为了计算。
发表于 2022-09-16 21:30:23
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-15 16:53:39
-
2022-09-15 15:45:16
-
2022-09-03 18:32:20
-
2022-09-02 16:03:44 -
2022-08-31 21:32:14
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
