题解 | #将满二叉树转换为求和树#

import java.util.; import java.io.; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); in.readLine(); String s = in.readLine(); String[] str = s.split(" "); int[] res = new int[str.length]; for(int i = 0;i < str.length;i ++){ res[i] = Integer.parseInt(str[i]); } dfs(res,0,str.length - 1); for(int i : res){ System.out.print(i+" "); }

}
public static int dfs(int[] res,int left,int right){
    
    if(left == right){
        int temp = 0;
        temp = res[left];
        res[left] = 0;
        return temp;
    }
    int mid =  (right - left) / 2 + left;
    int leftSum = dfs(res,left,mid-1);
    int rightSum = dfs(res,mid+1,right);
    int temp = res[mid];
    res[mid] = leftSum + rightSum;
    return temp + res[mid];
}

} // import java.util.; // import java.io.; // public class Main{ // public static void main(String[] args)throws IOException{ // BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); // bf.readLine(); // String s = bf.readLine();

// String[] inOrder = s.split(" "); // int[] res = new int[inOrder.length];

// for(int i = 0; i < inOrder.length; i++){ // res[i] = Integer.valueOf(inOrder[i]); // }

// dfs(res, 0, inOrder.length - 1);

// for (int r : res) System.out.print(r + " "); // }

// public static int dfs(int[] res, int left, int right){ // if(left == right){ // int temp = res[left]; // res[left] = 0; // return temp; // }

// int mid = (right - left) / 2 + left; // int leftSum = dfs(res, left, mid - 1); // int rightSum = dfs(res, mid + 1, right); // int temp = res[mid]; // res[mid] = leftSum + rightSum; // return res[mid] + temp; // } // }