leetcode 515 题解

一般来说,不想怎么写题解,因为不能穷尽所有的解法。解这个题过程中,有些有意思的地方,顺便就记录一下。原题在这里,我直接写答案了。

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 次。

dfs

深度优先遍历的方式,所有的节点只遍历一次,所以会更快一点。

var largestValues = function(root) {
    let arr = []
    
    function fn(node, i) {
        if(!node) return
        
        arr[i] = Math.max(node.val, arr[i] ?? -Infinity)
        
        fn(node.left, i + 1)
        fn(node.right, i + 1)
    }
    
    fn(root,0)
    
    return arr
}

这个答案,代码更简洁,运行更快。同时用到了新的操作符 ??,是不是很酷。

作者: 曾小乱

喜欢写点有意思的东西

《leetcode 515 题解》有一个想法

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据