Swift | LeetCode

Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard

Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

👨‍💻

Алгоритм:

1⃣Разбор строки:
Пройдите по строке, чтобы определить уровни узлов и их значения. Используйте два счетчика: один для отслеживания текущего уровня (количество тире), второй для значения узла.

2⃣Создание узлов:
Создайте новые узлы на основе уровня и значения из строки. Для каждого нового узла найдите его родительский узел из стека и добавьте узел как левого или правого ребенка.

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
    }
}

class Solution {
    func recoverFromPreorder(_ S: String) -> TreeNode? {
        var stack = [TreeNode]()
        let chars = Array(S)
        var i = 0
        
        while i < chars.count {
            var level = 0
            while i < chars.count && chars[i] == "-" {
                level += 1
                i += 1
            }
            
            var value = 0
            while i < chars.count && chars[i].isNumber {
                value = value * 10 + chars[i].wholeNumberValue!
                i += 1
            }
            
            let node = TreeNode(value)
            if level == stack.count {
                if !stack.isEmpty {
                    stack.last?.left = node
                }
            } else {
                while level != stack.count {
                    stack.removeLast()
                }
                stack.last?.right = node
            }
            stack.append(node)
        }
        
        while stack.count > 1 {
            stack.removeLast()
        }
        
        return stack.first
    }
}

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

Please open Telegram to view this post

VIEW IN TELEGRAM

178 views16:01