Задача: 894. All Possible Full Binary Trees
Сложность: medium

Учитывая целое число n, верните список всех возможных полных бинарных деревьев с узлами. Каждый узел каждого дерева в ответе должен иметь Node.val == 0. Каждый элемент ответа является корневым узлом одного возможного дерева. Вы можете вернуть конечный список деревьев в любом порядке. Полное бинарное дерево - это бинарное дерево, в котором каждый узел имеет ровно 0 или 2 дочерних.

Пример:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

👨‍💻 Алгоритм:

1⃣Если n четное, вернуть пустой список, так как полное бинарное дерево не может иметь четное количество узлов.

2⃣Если n == 1, вернуть дерево с одним узлом. Для всех возможных значений i от 1 до n-1 с шагом 2: Создать левое поддерево с i узлами. Создать правое поддерево с n-1-i узлами. Объединить все комбинации левого и правого поддеревьев с новым корнем, добавив их в список результатов.

3⃣Вернуть список результатов.

😎 Решение:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = 0; }
}

class Solution {
    public List<TreeNode> allPossibleFBT(int n) {
        if (n % 2 == 0) return new ArrayList<>();
        if (n == 1) return Arrays.asList(new TreeNode(0));
        
        List<TreeNode> result = new ArrayList<>();
        for (int i = 1; i < n; i += 2) {
            List<TreeNode> leftTrees = allPossibleFBT(i);
            List<TreeNode> rightTrees = allPossibleFBT(n - 1 - i);
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        return result;
    }

Ставь 👍 и забирай 📚 Базу знаний