Sponsored
Sponsored
This approach leverages the recursive nature of trees to calculate the depth. For each node, if it has no children, it is a leaf and has depth 1. Otherwise, recursively calculate the depth of each child and take the maximum depth found among all children, adding 1 for the current node to account for the path to parent.
The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited once. The space complexity is O(h) where h is the height of the tree, representing the function call stack during the recursion.
1class Node {
2 constructor(val, children = []) {
3 this.val = val;
4 this.children = children;
5 }
6}
7
8function maxDepth(root) {
9 if (!root) return 0;
10 if (root.children.length === 0) return 1;
11 let maxChildDepth = 0;
12 for (let child of root.children) {
13 maxChildDepth = Math.max(maxChildDepth, maxDepth(child));
14 }
15 return 1 + maxChildDepth;
16}In this JavaScript solution, a recursive approach similar to the Python solution is used. We iterate over each child and calculate their maximum depth recursively, updating the maximum depth found. We add 1 to the result to include the current node.
This approach utilizes BFS using a queue to iteratively compute tree depth. Nodes are enqueued level by level. At each level, we count its nodes, dequeuing them and enqueueing their children, indicating traversing to the next tree level. We increment a level counter as we progress deeper into the tree.
The time complexity is O(n) as we process each node once. The space complexity is O(n) for holding nodes of the widest level in the queue.
1using System.Collections.Generic;
public class Node {
public int val;
public IList<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
children = new List<Node>();
}
public Node(int _val, IList<Node> _children) {
val = _val;
children = _children;
}
}
public class Solution {
public int MaxDepth(Node root) {
if (root == null) return 0;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
int depth = 0;
while (queue.Count > 0) {
int levelSize = queue.Count;
for (int i = 0; i < levelSize; i++) {
Node node = queue.Dequeue();
foreach (var child in node.children) {
queue.Enqueue(child);
}
}
depth++;
}
return depth;
}
}In C# implementation, BFS is utilized with a queue to count levels by enqueuing and processing node children, marking completion of each level with a depth counter increment.