Turn binary tree into list then turn the list back into a binary tree.

Question

Avi T · Accepted Answer

Swift:

func getArrayFrom(tree : BinaryTree)->[Int] {
    if tree.leftNode == nil && tree.rightNode == nil {
        return [tree.value]
    }
    
    var array = [Int]()
    if let leftNode = tree.leftNode {
        array.append(contentsOf: getArrayFrom(tree: leftNode))
    }
    array.append(tree.value)
    if let rightNode = tree.rightNode {
        array.append(contentsOf: getArrayFrom(tree: rightNode))
    }
    return array
}

func getTreeFromArray(array : [Int])->BinaryTree {
    if array.count == 1 {
        let firstItem = array[0]
        return BinaryTree(value: firstItem, rightNode: nil, leftNode: nil)
    }
    
    let middleIndex = array.count / 2
    let leftSide = Array(array[0...middleIndex-1])
    let rightSide = Array(array[middleIndex+1...array.count-1])
    
    let leftTree = getTreeFromArray(array: leftSide)
    let rightTree = getTreeFromArray(array: rightSide)
    return BinaryTree(value: array[middleIndex],rightNode: rightTree, leftNode: leftTree)
}

print(root.desc)
let array = getArrayFrom(tree: root) // convert to list
print(array)
let tree = getTreeFromArray(array: array) // convert back to tree
print(tree.desc)

Meta

Pregunta de entrevista de Meta

Respuesta de la entrevista

Empresas seguidas

Búsquedas de empleo