首页 > 其他 > 详细

构造树并判断是否对称

时间:2020-01-27 17:56:02      阅读:48      评论:0      收藏:0      [点我收藏+]

标签:math   asc   lse   shift   for   static   

技术分享图片
技术分享图片

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
}

构造树并判断是否对称

标签:math   asc   lse   shift   for   static   

原文:https://www.cnblogs.com/ygjzs/p/12236339.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号