Для заданного двоичного дерева создайте сбалансированное двоичное дерево поиска, состоящее из суммы каждого узла и его дочерних элементов.

Question

Я сделал для дерева, где есть только левый или правый, но не могу понять, что делать, когда у вас есть оба

Пример ввода:

6

6 10 20 1 51 43 -> inorder

1 10 6 20 43 51 -> preorder

Пример вывода:

20 6 51 131 94 36

Пример ввода:

5

40 60 30 20 50 -> inorder

50 20 30 60 40 -> предварительный заказ

Пример вывода:

100 40 200 150 130

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Try {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        ArrayList<Integer> in = new ArrayList<Integer>();
        ArrayList<Integer> pre = new ArrayList<Integer>();

        for (int i = 0; i < n; i++) {
            in.add(s.nextInt());
        }

        for (int j = 0; j < n; j++) {
            pre.add(s.nextInt());
        }

        System.out.println(in);
        System.out.println(pre);

        ArrayList<Integer> sum = new ArrayList<Integer>();
        ArrayList<Integer> left = new ArrayList<Integer>();
        ArrayList<Integer> right = new ArrayList<Integer>();

        int root = pre.get(0);

        int index = in.indexOf(root);

        for(int x = 0 ; x < index;x++) {
            left.add(in.get(x));
        }
        for(int y=index+1 ;y < n  ;y++) {
            right.add(in.get(y));
        }

        System.out.println(left);
        System.out.println(right);

        if(left.isEmpty()|| right.isEmpty()) {
            Collections.reverse(pre);
            System.out.println("rev pre is"+ pre);
            sum.add(pre.get(0));
        for(int g = 1 ; g < pre.size();g++) {
            sum.add(pre.get(g)+sum.get(g-1));
        }
        System.out.println("sum tree"+ sum);
        Collections.sort(sum);
        System.out.println("sorted sum is"+ sum);

        }else {

        }


    }
}