牛客网真题2019-17-将满二叉树转换二叉树

满二叉树，中序遍历就能还原二叉树，这算是本题的bug。
中序二叉满树到中序求和二叉树
参考归并排序的写法。

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
    //满二叉树，ints必为奇数，中间那个结点是根结点。返回值是左右子树和根节点的和。
    public static int ToSumTree(int start, int end, int[] tree){
        if(start == end - 1){
            int temp = tree[start];
            tree[start] = 0;
            return temp;
        }
        int mid = (end + start) / 2;
        int node = tree[mid];
        tree[mid] = ToSumTree(start, mid, tree) + ToSumTree(mid + 1, end, tree);
        return node + tree[mid];
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        sc.nextLine();
        String[] line = sc.nextLine().split(" ");
        int[] midFullTree;
        midFullTree = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
        ToSumTree(0, midFullTree.length, midFullTree);
        //        System.out.println(Arrays.toString(midFullTree));
        for(int i = 0; i < midFullTree.length; i++){
            System.out.print(midFullTree[i]);
            if(i<midFullTree.length-1){System.out.print(" ");}
        }
    }
}