Sponsored
Sponsored
The BFS approach involves traversing the tree level by level and keeping track of the largest value at each level. We employ a queue data structure to facilitate level-wise traversal and maintain a list to store the maximum values for each row.
Time Complexity: O(n) where n is the number of nodes in the tree, since each node is processed exactly once. Space Complexity: O(n) due to the storage required to keep the queue and the result array.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10class Solution {
11 public List<Integer> largestValues(TreeNode root) {
12 List<Integer> result = new ArrayList<>();
13 if (root == null) return result;
14
15 Queue<TreeNode> queue = new LinkedList<>();
16 queue.offer(root);
17
18 while (!queue.isEmpty()) {
19 int levelMax = Integer.MIN_VALUE;
20 int size = queue.size();
21 for (int i = 0; i < size; i++) {
22 TreeNode node = queue.poll();
23 levelMax = Math.max(levelMax, node.val);
24 if (node.left != null) queue.offer(node.left);
25 if (node.right != null) queue.offer(node.right);
26 }
27 result.add(levelMax);
28 }
29
30 return result;
31 }
32}In this Java solution, we use a Queue to traverse the tree level by level. Each time we process a level, we find the largest node value and add it to our result list. This implementation is robust and effective for handling the level-wise extraction of maximum node values.
The DFS approach involves recursively exploring each branch of the tree depth-first and leveraging the depth of recursion to determine the level of the tree. For each level not yet considered, the maximum value is initialized, or updated if a new larger value is found.
Time Complexity: O(n) where n is the number of nodes in the tree, since every node is visited once. Space Complexity: O(h) where h is the height of the tree due to recursion stack.
1from typing import Optional, List
2
This Python solution leverages a recursive DFS to explore each tree branch. At each depth, it records the highest value; if there’s no entry for the depth, it initializes one with the node’s value. Otherwise, it updates the maximum value for the depth if the current node surpasses it.