一般来说,不想怎么写题解,因为不能穷尽所有的解法。解这个题过程中,有些有意思的地方,顺便就记录一下。原题在这里,我直接写答案了。
bfs
简单的直觉,就是广度优先遍历。拿到每层的节点,保持在数组里,再求出最大的值。
var largestValues = function(root) {
let arr = []
if(!root) return arr
let stack = [root]
while(stack.length) {
let temp = []
let max = -Infinity
while(stack.length) {
let node = stack.pop()
let v = node.val
max = Math.max(v, max)
node.left && temp.push(node.left)
node.right && temp.push(node.right)
}
arr.push(max)
stack = temp
}
return arr
};
提交后,速度挺慢的,怎么回事呢?先把节点放入,再拿出来,相当于把整个树遍历了 2 次。
继续阅读“leetcode 515 题解”