Сложность: medium
Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.
Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:
Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.
Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].
Пример:
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
👨💻 Алгоритм:
1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].
2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.
3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.
😎 Решение:
class Solution {
var flipped = [Int]()
var index = 0
var voyage: [Int] = []
func flipMatchVoyage(_ root: TreeNode?, _ voyage: [Int]) -> [Int] {
flipped = []
index = 0
self.voyage = voyage
dfs(root)
if !flipped.isEmpty && flipped[0] == -1 {
flipped = [-1]
}
return flipped
}
func dfs(_ node: TreeNode?) {
if let node = node {
if node.val != voyage[index] {
flipped = [-1]
return
}
index += 1
if index < voyage.count && node.left != nil && node.left!.val != voyage[index] {
flipped.append(node.val)
dfs(node.right)
dfs(node.left)
} else {
dfs(node.left)
dfs(node.right)
}
}
}
}Ставь 👍 и забирай 📚 Базу знаний