Problem description:

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

https://assets.leetcode.com/uploads/2020/08/21/largest_e1.jpg

1
2
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:

1
2
Input: root = [1,2,3]
Output: [1,3]

Example 3:

1
2
Input: root = [1]
Output: [1]

Example 4:

1
2
Input: root = [1,null,2]
Output: [1,2]

Example 5:

1
2
Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree will be in the range [0, 104].
  • 231 <= Node.val <= 231 - 1

Solution:

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        # BFS
        if not root: return []
        queue = deque([root])
        res = []
        while queue:
            nextLevel = deque([])
            localMax = float('-inf')
            for i in range(len(queue)):
                front = queue.popleft()
                localMax = max(localMax, front.val)
                if front.left: nextLevel.append(front.left)
                if front.right: nextLevel.append(front.right)
            res.append(localMax)
            queue = nextLevel
        return res

DFS

have an result array, pass depth info

if array length smaller than depth, append current root.val

if res[depth] < root.val, replace it 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        '''
        DFS
        '''
        if not root: return []
        self.res = []
        self.dfs(root, 0)
        return self.res
        
    def dfs(self, root, depth):
        if not root: return
        if len(self.res) == depth:
            self.res.append(root.val)
        if self.res[depth] < root.val:
            self.res[depth] = root.val
        self.dfs(root.left, depth+1)
        self.dfs(root.right, depth+1)

time complexity: $O()$
space complexity: $O()$
reference:
related problem: