Блог

Главная - Вопросы по программированию - Swift: определение узлов в дереве

Swift: определение узлов в дереве

#swift #recursion

#swift #рекурсия

Вопрос:

Я абстрагировал свою проблему в файле playground, чтобы упростить обсуждение. Моя проблема в том, что мне нужно вычислить все значения узлов в дереве, которое имеет минимальное количество дочерних элементов. Я неправильно выполняю рекурсию. Результатом моего алгоритма является [1,9], но должно быть: [1,3,9]. Есть мысли?

 import Foundation

class TreeNode{

    var children: [TreeNode]?
    var value: Int

    init( value: Int, children: [TreeNode]?){
        self.value = value
        self.children = children
    }
}

let node11 = TreeNode(value: 11, children: nil)
let node10 = TreeNode(value: 10, children: nil)
let node9 = TreeNode(value: 9, children: [node10, node11])
let node8 = TreeNode(value: 8, children: nil)
let node7 = TreeNode(value: 7, children: [node9])
let node6 = TreeNode(value: 6, children: [node8])
let node5 = TreeNode(value: 5, children:nil)
let node4 = TreeNode(value: 4, children: [node7])
let node3 = TreeNode(value: 3, children: [node5, node6])
let node2 = TreeNode(value: 2, children: [node4])
let node1 = TreeNode(value: 1, children: [node2,node3])
let node0 = TreeNode(value: 0, children: [node1])


func valueOfNodes(minNumberOfChildren: Int, node: TreeNode, tempResult: [Int])->[Int]{

    var result = tempResult

    guard let children = node.children else{
        return result
    }

    if children.count >= minNumberOfChildren{
        result.append(node.value)
    }

    for child in children{
        return valueOfNodes(minNumberOfChildren: minNumberOfChildren, node: child, tempResult: result)
    }

    return result
}


let result = valueOfNodes(minNumberOfChildren: 2, node: node0, tempResult: [])
print(result)

Комментарии:

1. Рассмотрите возможность использования пустого массива вместо nil для листьев. Это упростит работу с узлами и удалит избыточные средства защиты

2. этот пример является абстракцией моей реальной проблемы. Вот почему я добавил необязательный.

Ответ №1:

Вы всегда возвращаете результат только для первого дочернего элемента:

 for child in children{
    return valueOfNodes(minNumberOfChildren: minNumberOfChildren, node: child, tempResult: result)
}

Вместо этого вам нужно объединить их

 let childrenResult = children.flatMap { child in
    return valueOfNodes(minNumberOfChildren: minNumberOfChildren, node: child, tempResult: [])
}
result.append(contentsOf: childrenResult)

Такой подход убивает оптимизацию хвостовой рекурсии, но я не думаю, что вы можете использовать его здесь, поскольку результат родительского элемента зависит от результатов всех дочерних элементов.