Задача: 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⃣Вернуть список результатов.

😎 Решение:

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func allPossibleFBT(_ n: Int) -> [TreeNode?] {
    if n % 2 == 0 {
        return []
    }
    if n == 1 {
        return [TreeNode(0)]
    }
    
    var result = [TreeNode]()
    for i in stride(from: 1, to: n, by: 2) {
        let leftTrees = allPossibleFBT(i)
        let rightTrees = allPossibleFBT(n - 1 - i)
        for left in leftTrees {
            for right in rightTrees {
                result.append(TreeNode(0, left, right))
            }
        }
    }
    return result

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