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.
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.