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.
1#include <vector>
2#include <queue>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8struct TreeNode {
9 int val;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode() : val(0), left(nullptr), right(nullptr) {}
13 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
15};
16
17vector<int> largestValues(TreeNode* root) {
18 if (!root) return {};
19
20 vector<int> result;
21 queue<TreeNode*> q;
22 q.push(root);
23
24 while (!q.empty()) {
25 int levelMax = INT_MIN;
26 int size = q.size();
27 for (int i = 0; i < size; ++i) {
28 TreeNode* node = q.front(); q.pop();
29 levelMax = max(levelMax, node->val);
30 if (node->left) q.push(node->left);
31 if (node->right) q.push(node->right);
32 }
33 result.push_back(levelMax);
34 }
35
36 return result;
37}This C++ solution employs a breadth-first search (BFS) strategy using the queue container. For each level of nodes in the binary tree, it computes the maximum value and appends it to the result vector. The algorithm effectively traverses each level of the binary tree exactly once.
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.