将满二叉树转换为求和树

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;}
}

import java.util.*;
/*
    主要是对于二叉树前序遍历和中序遍历关系转换的理解，对于每个求和节点
    脑海中需要构想出空间位置关系
*/
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] str1 = sc.nextLine().trim().split(" ");
        String[] str2 = sc.nextLine().trim().split(" ");
        
        int[] prevSeq = new int[str1.length];
        int[] inSeq = new int[str2.length];
        boolean[] boolArr = new boolean[str1.length];// 布尔型数组，标记已求和的节点
        int[] inSeqRes = new int[str1.length];    // 记录中序遍历的结果求和树
        
        for(int i = 0;i < prevSeq.length;i++){
            prevSeq[i] = Integer.parseInt(str1[i]);
            inSeq[i] = Integer.parseInt(str2[i]);
        }
        
        for(int i = 0;i < prevSeq.length;i++){
            func(prevSeq[i],inSeq,boolArr,inSeqRes);
        }
        
        for(int i: inSeqRes){
            System.out.print(i+" ");
        }
        System.out.println();
    }
    
    public static void func(int node, int[] inSeq,boolean[] boolArr, int[] inSeqRes){
        int index = -1;// index为在中序遍历中找到的需要求和的节点
        for(int i = 0;i < inSeq.length;i++){
            if(inSeq[i] == node){
                index = i;
                boolArr[index] = true;
                break;
            }
        }
        
        if(index == -1)
            return;// 没有找到就返回
        
        // 对求和节点的左右子树求和
        int sum = 0;
        for(int i = 0;i < index;i++){
            if(boolArr[i]){
                continue;// 对于已经标记的节点（已求和），必定是上层节点，直接跳过
            }
            sum += inSeq[i];
        }
        
        for(int i = index + 1;i < inSeq.length;i++){
            if(boolArr[i]){
                break;
            }
            sum += inSeq[i];
        }
        
        inSeqRes[index] = sum;
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> preorder  = new ArrayList<>();
        String s = sc.nextLine();
        String[] ss = s.split(" ");
        for(int i = 0 ; i <ss.length;i++){
            preorder.add(Integer.valueOf(ss[i]));
        }
        ArrayList<Integer> inorder = new ArrayList<>();
        s = sc.nextLine();
        ss = s.split(" ");
        for(int i = 0 ; i <ss.length;i++){
            inorder.add(Integer.valueOf(ss[i]));
        }
        getSumTree(preorder,inorder);
        //res = new int[preorder.size()];
        System.out.println(getSumTree(preorder,inorder).trim());
    }
 
    public static String getSumTree(List<Integer> preorder,List<Integer> inorder){
        if(preorder==null||preorder.size()==0)return "";
        if(inorder==null||inorder.size()==0)return "";
        String res = "";
        int root = preorder.get(0);
        int root_idx = 0;
        for(int i = 0 ; i<inorder.size();i++){
            if(inorder.get(i) ==root){
                root_idx = i;
                break;
            }
        }
        res+= getSum(inorder,root_idx);
        //左子树
        res = getSumTree(preorder.subList(1,root_idx+1) , inorder.subList(0,root_idx)) +" "+res;
        //右子树
        res =res + getSumTree(preorder.subList(root_idx+1,preorder.size()) , inorder.subList(root_idx+1,inorder.size()));
        return res;
    }
 
    private static int getSum(List<Integer> inorder, int root_idx) {
        if(inorder==null)return 0 ;
        int sum = 0;
        for(int i = 0 ; i <root_idx;i++)sum+=inorder.get(i);
        for(int i = root_idx+1 ; i <inorder.size();i++)sum+=inorder.get(i);
        return sum;
    }
}

//只通过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;
    }
}