class TreeNode {
  constructor(value) {
    this.value = value; //数据域
    this.left = null; //左孩子
    this.right = null; //右孩子
  }
}

// 二叉树工具类
class BinaryTree {
  constructor() {}
  // 数组严格表示法
  static createTreeNode(arr, index) {
    if (index > arr.length) {
      return null;
    }
    if (arr[index] == null) {
      return null;
    }
    const node = new TreeNode(arr[index]);
    node.left = BinaryTree.createTreeNode(arr, index * 2 + 1);
    node.right = BinaryTree.createTreeNode(arr, index * 2 + 2);
    return node;
  }

  // 数组优化表示法
  static arrayToTree(arr) {
    if (arr.length === 0) {
      return null;
    }
    const root = new TreeNode(arr[0]);
    //是否是左孩子节点
    let isLChild = true;
    //用数组的push和shift模拟队列
    const queue = [];
    queue.push(root);

    //从第二个节点开始遍历
    for (let i = 1; i < arr.length; i++) {
      //从队列中取出第一个元素
      const node = queue[0];
      if (isLChild) {
        if (arr[i] != null) {
          node.left = new TreeNode(arr[i]);
          //把 left 节点插入队列
          queue.push(node.left);
        }
        // left 完毕，开始处理 right
        isLChild = false;
      } else {
        if (arr[i] != null) {
          node.right = new TreeNode(arr[i]);
          //把 right 节点插入队列
          queue.push(node.right);
        }
        //right处理完毕，开始出队列
        queue.shift();
        isLChild = true;
      }
    }
    return root;
  }
}