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 def __init__(self, val=None, children=None):
3 self.val = val
4 self.children = children if children is not None else []
5
6
7def maxDepth(root: 'Node') -> int:
8 if not root:
9 return 0
10 if not root.children:
11 return 1
12 return 1 + max(maxDepth(child) for child in root.children)The function maxDepth is implemented recursively. We check if the root is None and return 0 which indicates an empty tree. If the node has no children, return 1, indicating it is a leaf. For a node with children, recursively calculate the max depth for each child and add 1 to the result to represent 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.
1#include <queue>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
class Solution {
public:
int maxDepth(Node* root) {
if (!root) return 0;
queue<Node*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
Node* node = q.front();
q.pop();
for (Node* child : node->children) {
q.push(child);
}
}
depth++;
}
return depth;
}
};C++ uses a queue to perform BFS, visiting each node level by level and enqueuing their children. The depth variable is incremented every time a full level is processed.