给定深度的节点的快速二叉树列表

debugcn 发表于 Dev

黎庆荣

我正在为二叉树编写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
    }

我们如何实现所需的功能？

萨钦·瓦斯（Sachin Vas）

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
    }

这是解决方案之一。假设自身是根节点。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。