前端就该用JS写算法1

题目

二叉树的最大宽度

/**
 * @分析 --- 超时了
 * 1. 层序遍历，然后记住每一层的值的数量，求那个最大的值
 * 2. 宽度是左右节点之间的长度，所以右节点之后的 null 是可以忽略的,每次从队列中出队钱，要先取出队列中右侧的 null
 */
//  清除左右节点的 null 节点
const deleteNull = arr => {
    while (arr.length && !arr[0]) {
        arr.shift()
    }
    while (arr.length && !arr[arr.length - 1]) {
        arr.pop()
    }
    return arr
}
var widthOfBinaryTree = function (root) {
    if (!root) return 0
    let queue = []
    let max = 1
    queue.push(root)
    while (queue.length) {
        queue = deleteNull(queue)
        let len = queue.length
        if (!len) return max
        max = Math.max(max, len)
        while (len--) {
            const root = queue.shift()
            if (!root) {
                queue.push(null, null)
            } else {
                queue.push(root.left, root.right)
            }
        }
    }
    return max
};
/**
 * @分析
 * 1. 用完全二叉树的方式来求
 * 2. 每次除了存节点，还得存一下对应 pos(类似下标的值，根节点是1),
 * 3. 这样求每一层的宽度，只需要求第一个和最后一个非空节点，两者 pos 相减即可。
 * @注意
 * 1. 如果两个炒鸡大的数相减，会得到 NaN，从而报错；
 * 2. 一般情况下是不会出现那么大的树的，但是当树的层级比较高的时候，而每一层的 pos 值都是 2^n-1,就会有概率超出
 * 
 */
var widthOfBinaryTree = function (root) {
    if (!root) return 0
    let res = 0
    let queue = []
    let level = 0 // 记录当前层，用来判断左节点
    let cur_level = 0 // 当前层
    queue.push([1, root])
    while (queue.length) {
        let len = queue.length // 当前层的长度
        level++ // 每一次循环都是加一层
        // 开始当前层的遍历
        let left
        while (len--) {
            // 弹出节点
            const [pos, root] = queue.shift()
            if (root) {
                queue.push([2 * pos, root.left])
                queue.push([2 * pos + 1, root.right])
                // 第一个存在节点，就是左节点
                if (level !== cur_level) {
                    // 左节点
                    cur_level = level
                    left = pos
                }
                // 每一个节点都比较一下，就不要判断哪个是最右节点了，因为有可能数组最后节点是 null
                res = Math.max(res, pos - left + 1)
            }
        }
    }
    return res
}

一个不太美好的开始

本来今天做完 2021 年的第一天，早起第一天，算法第一天，应该来个比较的好的结果才对的，但是实际情况是，题把我卡住了。超时了，然后继续搞，解答错误了。

分析了一下就是每一层的 pos 都是 2 的指数级别的，当树以单个节点一直往下传递，层数比较大的时候，左右节点的 pos 就是一个超级大数，这个时候两个值相减，就会出错。

然后我尝试用 BigInt 的方式去弄，然后1h过去了，2h也快了，还是没处理完

本来这个属于一个限时学习过程，思考了一下，觉得有遗憾的开场也未尝不可，毕竟我也不能保证接下来的 300 天每天都能成功，但是失败了也是一种学习的过程呀。

重新定下规矩吧

• 每天早起做题属于持续学习，最多不能超过1.5h
• 如果当天的题目没有成功，则保存起来，在那一周的周末完成，并标注好哪一天失败的题目即可。
• 不能因为一道题而把整天计划给断掉

2021 我们一起加油啊