Быстрое двоичное дерево списка узлов на заданной глубине

Question

Привет Я пишу быстрый алгоритм для двоичного дерева. Моя цель состоит в том, чтобы создать список узлов на определенной глубине что-то вроде

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 
    } 

Как мы можем достичь функции желания? Любое предложение очень ценит. Благодаря!

Answer 1

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 
    } 

Это одно из решений. Предполагая, что сам является корневым узлом.