Open sl1673495 opened 4 years ago
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row 您需要在二叉树的每一行中找到最大的值。
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
这是一道典型的 BFS 题目,BFS 的套路其实我是知道的,维护一个 queue 队列,在读取子节点的时候同时把孙子节点 push 到队列中,那么就可以实现广度优先遍历。
但是这里有一个问题卡住我了一会,就是如何知道当前处理的节点是哪个层级的,在最开始的时候我尝试写了一下二叉树求某个 index 所在层级的公式,但是发现这种公式只能处理「平衡二叉树」。
后面看题解发现他们都没有专门维护层级,再仔细一看才明白层级的思路:
其实就是在每一轮 while 循环里,再开一个 for 循环,这个 for 循环的终点是「提前缓存好的 length 快照」,也就是进入这轮 while 循环时,queue 的长度。其实这个长度就恰好代表了「一个层级的长度」。
缓存后,for 循环里可以安全的把子节点 push 到数组里而不影响缓存的当前层级长度。
另外有一个小 tips,在 for 循环处理完成后,应该要把 queue 的长度截取掉上述的缓存长度。一开始我使用的是 queue.splice(0, len)
,结果速度只击败了 33%的人。后面换成 for 循环中去一个一个shift
来截取,速度就击败了 77%的人。
/**
* @param {TreeNode} root
* @return {number[]}
*/
var largestValues = function (root) {
if (!root) return [];
let queue = [root];
let maximums = [];
while (queue.length) {
let max = Number.MIN_SAFE_INTEGER;
// 这里需要先缓存length 这个length代表当前层级的所有节点
// 在循环开始后 会push新的节点 length就不稳定了
let len = queue.length;
for (let i = 0; i < len; i++) {
let node = queue[i];
max = Math.max(node.val, max);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
// 本「层级」处理完毕,截取掉。
for (let i = 0; i < len; i++) {
queue.shift();
}
// 这个for循环结束后 代表当前层级的节点全部处理完毕
// 直接把计算出来的最大值push到数组里即可。
maximums.push(max);
}
return maximums;
};
interface Option<S, G> {
state: S
getters: {
[K in keyof G]: (state: S) => G[K]
}
}
interface Dispatch<G, T extends keyof G> {
(type: T): G[T]
}
const create = <S, G, T extends keyof G>(
option: Option<S, G>,
): Dispatch<G, T> => {
option
return (() => {}) as any
}
const dispatch = create({
state: {
count: 1,
},
getters: {
countPlus(state) {
return state.count + 1
},
},
})
// number
const countPlus = dispatch("countPlus")
export { countPlus }
首先要用 Option 这个类型把 G 的类型给推断好,从 getter: { count: () => number }
推断成 getter: { count: number }
。
然后有个技巧,就是新开一个泛型 T extends keyof G,这样在 dispatch 里就可以直接把 type 定义成 T 类型,也就只可以 dispatch getters 里的 key。
https://github.com/preactjs/preact/blob/master/hooks/src/index.js
Preact 里的 Hook 实现相对来说比较简洁易懂,没有React 里那么多复杂的调度机制相关的干扰。并且在 js 里使用 d.ts 里的类型也比较值得学习,一些没有办法用 ts 重构的老项目可以用这个方法给一些比较重要的工具加类型。