Lstmxx的空间

919. 完全二叉树插入器

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

• CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
• CBTInserter.get_root() 将返回树的头节点。

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

class CBTInserter {
    head: TreeNode
    parents: TreeNode[]
    i: number
    constructor(root: TreeNode | null) {
      this.head = root
      this.i = 0
      const nodeQue = [this.head]
      let depth = 0
      while(nodeQue.length) {
        depth++
        const nodes = nodeQue.splice(0)
        const len = nodes.length
        let lastIndex = -1
        for(let i = 0;i < len; i++) {
          const node = nodes[i]
          if (node.left && node.right) {
            lastIndex = i
          }
          if (node.left) {
            nodeQue.push(node.left)
          }
          if (node.right) {
            nodeQue.push(node.right)
          }
        }
        // 如果下一层不满足完成二叉树叶子结点数量，则父节点列表为nodes
        if (nodeQue.length !== 2 ** depth) {
          this.parents = nodes
          this.i = lastIndex === -1 ? 0 : lastIndex + 1
          break
        }
      }
    }

    insert(v: number): number {
      
      if (this.parents.length === this.i) {
        this.parents = this.parents.reduce((pre, node) => {
          node.left && pre.push(node.left)
          node.right && pre.push(node.right)
          return pre
        }, [])
        this.i = 0
      }
      
      if (this.parents[this.i].left === null) {
        this.parents[this.i].left = new TreeNode(v)
        return this.parents[this.i].val
      }
      if (this.parents[this.i].right === null) {
        this.parents[this.i].right = new TreeNode(v)
        return this.parents[this.i++].val
      }

    }

    get_root(): TreeNode | null {
      return this.head
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * var obj = new CBTInserter(root)
 * var param_1 = obj.insert(v)
 * var param_2 = obj.get_root()
 */