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.
1#include <vector>
2#include <algorithm>
3#include <climits>
4
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
void dfs(TreeNode* node, int depth, vector<int>& maxValues) {
if (!node) return;
if (depth == maxValues.size()) {
maxValues.push_back(node->val);
} else {
maxValues[depth] = max(maxValues[depth], node->val);
}
dfs(node->left, depth + 1, maxValues);
dfs(node->right, depth + 1, maxValues);
}
vector<int> largestValues(TreeNode* root) {
vector<int> maxValues;
dfs(root, 0, maxValues);
return maxValues;
}This C++ solution employs a depth-first search (DFS) paradigm using recursion. We track the depth to associate the maximum value found at each level. If a given depth isn’t present in the list of maximum values, it initializes it; otherwise, it updates the level’s maximum with the current node’s value if it exceeds the current maximum.