我正在为二叉树编写 Swift 算法。我的目标是在特定深度创建一个节点列表,例如
func listNodeAt(_n: Int) --> [T] {
}
这是我的树类
public class BinaryTreeNode<T:Comparable> {
//Value and children vars
public var value:T
public var leftChild:BinaryTreeNode?
public var rightChild:BinaryTreeNode?
public weak var parent:BinaryTreeNode?
//Initialization
public convenience init(value: T) {
self.init(value: value, left: nil, right: nil, parent:nil)
}
public init(value:T, left:BinaryTreeNode?, right:BinaryTreeNode?, parent:BinaryTreeNode?) {
self.value = value
self.leftChild = left
self.rightChild = right
self.parent = parent
}
}
我已经构建了一个辅助函数来计算节点的深度
//Depth
public func depth() -> Int {
guard var node = parent else {
return 0
}
var depth = 1
while let parent = node.parent {
depth = depth + 1
node = parent
}
return depth
}
怎样才能实现想要的功能?
最佳答案
func listNodeAt(_ n: Int) -> [T] {
return getElementsAt(n, node: self)
}
private func getElementsAt(_ n: Int, node: BinaryTreeNode<T>, traversingDepth: Int = 0) -> [T] {
var array = Array<T>()
if traversingDepth < n {
if let left = node.leftChild {
array = array + getElementsAt(n, node: left, traversingDepth: traversingDepth + 1)
}
if let right = node.rightChild {
array = array + getElementsAt(n, node: right, traversingDepth: traversingDepth + 1)
}
} else if traversingDepth == n {
array.append(node.value)
}
return array
}
这是解决方案之一。这里假设self是根节点。
关于给定深度节点的 Swift 二叉树列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42264678/