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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<int> LargestValues(TreeNode root) {
13 List<int> result = new List<int>();
14 if (root == null) return result;
15
16 Queue<TreeNode> queue = new Queue<TreeNode>();
17 queue.Enqueue(root);
18
19 while (queue.Count > 0) {
20 int levelMax = Int32.MinValue;
21 int size = queue.Count;
22 for (int i = 0; i < size; ++i) {
23 TreeNode node = queue.Dequeue();
24 levelMax = Math.Max(levelMax, node.val);
25 if (node.left != null) queue.Enqueue(node.left);
26 if (node.right != null) queue.Enqueue(node.right);
27 }
28 result.Add(levelMax);
29 }
30
31 return result;
32 }
33}In this C# solution, we implement a level-order traversal using a Queue to keep track of nodes at each level. For every level, the largest value is determined and added to the results list. This strategy allows for a clean solution to the problem.
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.