Find Largest Value in Each Tree Row

Intuition

Do a DFS and in the process use an additional variable depth to mark the depth of current node. Then, when visiting each node, compare the node's value with the maximum value of current depth and update it if necessary.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        self.largest = []
        self._dfs(root, 0)
        return self.largest

    def _dfs(self, node, depth):
        if node is None:
            return
        if len(self.largest) <= depth:
            self.largest.append(node.val)
        else:
            self.largest[depth] = max(self.largest[depth], node.val)
        self._dfs(node.left, depth + 1)
        self._dfs(node.right, depth + 1)