構造樹並判斷是否對稱

class Node {
  constructor (val) {
    this.val = val
    this.left = this.right = undefined
  }
}
class Tree {
  constructor (data) {
    // 臨時存儲所有節點
    let nodeList = []
    // 根節點
    let root
    for (let i = 0, len = data.length; i < len; i++) {
      let node = new Node(data[i])
      nodeList.push(node)
      if (i > 0) {
        // 記錄當前節點屬於哪一層
        let n = Math.floor(Math.sqrt(i + 1))
        // 記錄當前層的起始點
        let q = Math.pow(2, n) - 1
        // 記錄上一層的起始點
        let p = Math.pow(2, n - 1) - 1
        let parent = nodeList[p + Math.floor((i - q) / 2)]
        // 將當前節點和上一層的父節點做關聯
        if (parent.left) {
          parent.right = node
        } else {
          parent.left = node
        }
      }
    }
    root = nodeList.shift()
    nodeList.length = 0
    return root
  }
  static isSymmetry (root) {
    if (!root) {
      return true
    }
    let walk = (left, right) => {
      if (!left && !right) {
        return true
      }
      if ((left && !right) || (!left && right) || (left.val !== right.val)) {
        return false
      }
      return walk(left.left, right.right) && walk(left.right, right.left)
    }
    return walk(root.left, root.right)
  }
}

export default Tree

export {
  Node
}