Binary Tree - Swift 相关实现

原文参考

节点

class Node {
    
    var value: Int
    var left: Node?
    var right: Node?
    
    init(_ value:Int) {
        self.value = value
    }

}

翻转二叉树

func invert(_ tree: Node?) {
    
    guard let tree = tree else {return}

    (tree.left,tree.right) = (tree.right,tree.left)

    invert(tree.left)
    invert(tree.right)
    
}

前序遍历

func visit(_ tree:Node?){
    
    guard let tree = tree else {return}
    
    print(tree.value)
    visit(tree.left)
    visit(tree.right)

}

中序遍历

func visit(_ tree:Node?){
    
    guard let tree = tree else {return}
    
    visit(tree.left)
    print(tree.value)
    visit(tree.right)

}

后序遍历

func visit(_ tree:Node?){
    
    guard let tree = tree else {return}
    
    visit(tree.left)
    visit(tree.right)
    print(tree.value)

}

层次遍历/广度优先遍历

func visit(_ tree:Node?){
    
    guard let tree = tree else {return}

    var queue = [Node]()
    queue.append(tree)
    
    while !queue.isEmpty {

        let node = queue.removeFirst()

        print(node.value)

        if let left = node.left {
            queue.append(left)
        }
        if let right = node.right{
            queue.append(right)
        }
        
    }

}

深度优先遍历

func visit(_ tree:Node?){

    guard let tree = tree else {return}
    
    var stack = [Node]()
    stack.append(tree)

    while !stack.isEmpty {
        
        let node = stack.removeLast()
        
        print(node.value)

        if let right = node.right {
            stack.append(right)
        }
        if let left = node.left{
            stack.append(left)
        }
        
    }
}

判断二叉排序树

func isBinarySortTree(_ tree:Node?)->Bool{
    
    var lastValue = Int.min
    
    
    func isBinarySortTree(_ tree:Node?,_ lastValue:inout Int) -> Bool {
        
        
        guard let tree = tree else {
            return true
        }
        
        guard isBinarySortTree(tree.left,&lastValue) else {
            return false
        }
        
        
        guard lastValue < tree.value else {
            return false
        }
        
        lastValue = tree.value
        
        guard isBinarySortTree(tree.right,&lastValue) else {
            return false
        }
        
        return true
        
    }
    
    return isBinarySortTree(tree, &lastValue)
}