Задача: 114. Flatten Binary Tree to Linked List
Сложность: Medium

"Связный список" должен использовать тот же класс TreeNode, где указатель на правого ребенка указывает на следующий узел в списке, а указатель на левого ребенка всегда равен null.
"Связный список" должен быть в том же порядке, что и обход бинарного дерева в прямом порядке.

Пример:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

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

1⃣Плоское преобразование дерева: Рекурсивно преобразуем левое и правое поддеревья заданного узла, сохраняя соответствующие конечные узлы в leftTail и rightTail.

2⃣Установка соединений: Если у текущего узла есть левый ребенок, выполняем следующие соединения:
leftTail.right = node.right
node.right = node.left
node.left = None

3⃣Возврат конечного узла: Возвращаем rightTail, если у узла есть правый ребенок, иначе возвращаем leftTail.

😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Solution {
    func flattenTree(_ node: TreeNode?) -> TreeNode? {
        guard let node = node else {
            return nil
        }
        if node.left == nil && node.right == nil {
            return node
        }
        let leftTail = flattenTree(node.left)
        let rightTail = flattenTree(node.right)
        if let leftTail = leftTail {
            leftTail.right = node.right
            node.right = node.left
            node.left = nil
        }
        return rightTail ?? leftTail
    }

    func flatten(_ root: TreeNode?) {
        _ = flattenTree(root)
    }
}

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