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 <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5// Definition for a binary tree node.
6struct TreeNode {
7 int val;
8 struct TreeNode *left;
9 struct TreeNode *right;
10};
11
12#define MAX_QUEUE_SIZE 10000
13
14struct TreeNode* queue[MAX_QUEUE_SIZE];
15int front = 0;
16int rear = 0;
17
18void enqueue(struct TreeNode* node) {
19 if (rear < MAX_QUEUE_SIZE) {
20 queue[rear++] = node;
21 }
22}
23
24struct TreeNode* dequeue() {
25 return queue[front++];
26}
27
28int* largestValues(struct TreeNode* root, int* returnSize) {
29 if (!root) {
30 *returnSize = 0;
31 return NULL;
32 }
33
34 int* result = (int*)malloc(sizeof(int) * MAX_QUEUE_SIZE);
35 *returnSize = 0;
36
37 front = rear = 0;
38 enqueue(root);
39 while (front != rear) {
40 int levelSize = rear - front;
41 int levelMax = INT_MIN;
42 for (int i = 0; i < levelSize; ++i) {
43 struct TreeNode* node = dequeue();
44 if (node->val > levelMax) {
45 levelMax = node->val;
46 }
47 if (node->left) {
48 enqueue(node->left);
49 }
50 if (node->right) {
51 enqueue(node->right);
52 }
53 }
54 result[(*returnSize)++] = levelMax;
55 }
56
57 return result;
58}This solution uses a queue to perform a BFS traversal on the binary tree. Each level is processed entirely before moving to the next, and the largest value encountered at each level is recorded in the result array. The function returns the array of largest values and updates the size of the returned array via the pointer returnSize.
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.
1import java.util.*;
2
This Java solution adopts a recursive DFS strategy. For each node, it utilizes the current recursion depth to determine the level for updating the maximum node value. New levels add an entry to the maxValues list, while existing levels update the maximum based on new node values.