/*
#### 问题：
将一个从小到大排列好的数组转换成二叉搜索树。

#### 思路：
由于是从小到大排列好的数组，通过观察发现，每次取数组中间的元素（平衡时向右取），可以得到一个根节点，以及左右两颗子树。
然后分别对子树做同样的操作，并将子树的根节点按二叉搜索树的要求，作为前面根节点的左右节点。
不断对左右子树进行递归操作，最终可以得到一颗二叉搜索树。
*/

class ArrObject {
  constructor(arr) {
    this.arr = arr

    let middleIndex = this.arr.length % 2 === 0 ? this.arr.length / 2 : parseInt(this.arr.length / 2, 10)
    this.middle = arr[middleIndex]

    this.leftArr = this.arr.slice(0, middleIndex)
    this.rightArr = this.arr.slice(middleIndex + 1)
  }
}

class Node {
  constructor(arrObject) {
    this.data = arrObject.middle

    if (arrObject.leftArr.length > 0) {
      this.left = new Node(new ArrObject(arrObject.leftArr))
    }

    if (arrObject.rightArr.length > 0) {
      this.right = new Node(new ArrObject(arrObject.rightArr))
    }  
  }
}

class Tree {
  constructor(arr) {
    this.root = new Node(new ArrObject(arr))

    this.outs = []
  }

  print(curLevelNodes) {
    if (!curLevelNodes) {
      curLevelNodes = [this.root]
      this.outs.push(this.root.data + ' ')
      this.outs.push('| ')
    }

    let nextLevelNodes = []
    for (let i = 0; i < curLevelNodes.length; i++) {
      let curNode = curLevelNodes[i]

      if (curNode.left) {
        this.outs.push(curNode.left.data + ' ')
        nextLevelNodes.push(curNode.left)
      } else {
        this.outs.push('[] ')
      }

      if (curNode.right) {
        this.outs.push(curNode.right.data + ' ')
        nextLevelNodes.push(curNode.right)
      } else {
        this.outs.push('[] ')
      }
    }

    if (nextLevelNodes.length > 0) {
      this.outs.push('| ')
      this.print(nextLevelNodes)
    } else {
      console.log(this.outs.slice(0, this.outs.lastIndexOf('| ')).join(''))
    }
  }
}

var arr = [10, 15, 20, 30, 40, 50, 80, 90, 100, 200, 260]
var tree = new Tree(arr)
tree.print()

var arr = [10, 15, 20, 30, 40, 50, 80, 90, 100, 200]
var tree = new Tree(arr)
tree.print()

/*
#### 问题：
将一个从小到大排列好的数组转换成二叉搜索树。

#### 思路：
- 先让数组按降序排列
- 因此，在往二叉树中添加结点的过程中，新的结点只会添加在最左边
- 通过观察发现，在失衡发生的时候，永远只需要左左旋转
- 还可以简化一些判断条件：高度的计算，失衡的计算。
*/

let addNode = (root, node) => {
  if (!root) {
    return node
  }
  root.left = addNode(root.left, node)

  if (root.left.height - (root.right ? root.right.height : -1) === 2) {
    root = singleRotateLeft(root)
  }
  
  root.height = root.left.height + 1

  return root
}

let singleRotateLeft = (root) => {
  let node = root.left
  root.left = node.right
  node.right = root

  root.height = (root.left ? root.left.height : -1) + 1
  node.height = (node.left ? node.left.height : -1) + 1

  return node
}

class Node {
  constructor(options) {
    this.data = options.data
    this.left = options.left || null
    this.right = options.right || null

    this.height = 0
  }
}

class Tree {
  constructor(list) {
    this.list = list.reverse()

    this.root = new Node({ data: this.list[0] })
    this.buildTree()

    this.outs = []
  }

  buildTree() {
    for (let i = 1; i < this.list.length; i++) {
      let node = new Node({ data: this.list[i] })
      this.add(node)
    }
  }

  add(node) {
    this.root = addNode(this.root, node)
  }

  print(curLevelNodes) {
    if (!curLevelNodes) {
      curLevelNodes = [this.root]
      this.outs.push(this.root.data + ' ')
      this.outs.push('| ')
    }

    let nextLevelNodes = []
    for (let i = 0; i < curLevelNodes.length; i++) {
      let curNode = curLevelNodes[i]

      if (curNode.left) {
        this.outs.push(curNode.left.data + ' ')
        nextLevelNodes.push(curNode.left)
      } else {
        this.outs.push('[] ')
      }

      if (curNode.right) {
        this.outs.push(curNode.right.data + ' ')
        nextLevelNodes.push(curNode.right)
      } else {
        this.outs.push('[] ')
      }
    }

    if (nextLevelNodes.length > 0) {
      this.outs.push('| ')
      this.print(nextLevelNodes)
    } else {
      console.log(this.outs.slice(0, this.outs.lastIndexOf('| ')).join(''));
    }
  }
}

var list = [10, 15, 20, 30, 40, 50, 80, 90, 100, 200, 260]
var tree = new Tree(list)
tree.print()

var list = [1, 3, 5, 7, 100, 1000, 1001]
var tree = new Tree(list)
tree.print()

var list = [-100, -1.1, 0, 666, 2333333]
var tree = new Tree(list)
tree.print()