Problem statement

https://leetcode.com/problems/find-largest-value-in-each-tree-row/

Solution

Either use bfs approach with O(n) time and O(W) memory, or use dfs approach, where we keep layers maximal elements. However it is better idea to use dfs here.

Complexity

Time complexity is also O(n) and space complexity is O(h), which we can not improve, because h is the size of output.

Code

class Solution:
    def largestValues(self, root):
        levels = []
        def dfs(node, k):
            if not node: return
            if len(levels) <= k:
                levels.append(node.val)
            else:
                levels[k] = max(levels[k], node.val)
            dfs(node.left, k+1)
            dfs(node.right, k+1)
            
        dfs(root, 0)
        return levels