剑指 Offer II 043. 往完全二叉树添加节点

定义：完全二叉树定义完全二叉树(Complete Binary Tree)若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
特性1：对于任意一个结点，不可能只存在右节点不存在左节点；
特性2：使用层序遍历法遍历整颗树，找到第一个没有两个子节点的节点，其左侧的所有节点均有两个节点，其右侧的节点，均为叶子节点；
特性3：向一棵完全二叉树中插入节点，插入节点的位置均为先左后右；

class CBTInserter {
    var rootNode :TreeNode?
    var nodeArray = Array<TreeNode>()

    
    init(_ root: TreeNode?) {
        
        rootNode = root
        var array = Array<TreeNode>()
        if let node = rootNode{
            array.append(node)
        }
        while !array.isEmpty {
            
            let tempNode = array.removeFirst()
            
            if tempNode.left == nil || tempNode.right == nil {
                nodeArray.append(tempNode)
            }
            
            
            if let leftNode = tempNode.left {
                array.append(leftNode)
            }
            
            if let rightNode = tempNode.right {
                array.append(rightNode)
            }
            
        }
        
        
        

    }
    
    func insert(_ v: Int) -> Int {
        
        let tempNode = nodeArray.first
        let insertNode = TreeNode(v)
        nodeArray.append(insertNode)

        if tempNode != nil {
            
            if tempNode?.left == nil {
                tempNode?.left = insertNode
            }
            else {
                tempNode?.right = insertNode
               nodeArray.removeFirst()
            }
        }
        return tempNode?.val ?? 0

        
    }
    
    func get_root() -> TreeNode? {
        return rootNode
    }
    
    
}