This is one of those problems where the clean idea matters more than the amount of code. For 559. Maximum Depth of N-ary Tree, the solution in this repository is mainly a stack solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: stack.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maxDepth.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given a n-ary tree, find its maximum depth.
03
04The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
05
06For example, given a 3-ary tree:
07
08We should return its max depth, which is 3.
09
10Note:
11
12The depth of the tree is at most 1000.
13The total number of nodes is at most 5000.
14**/
15
16//Your runtime beats 11.70 % of cpp submissions.
17/*
18// Definition for a Node.
19class Node {
20public:
21 int val;
22 vector<Node*> children;
23
24 Node() {}
25
26 Node(int _val, vector<Node*> _children) {
27 val = _val;
28 children = _children;
29 }
30};
31*/
32class Solution {
33public:
34 int maxDepth(Node* root) {
35 if(root==NULL) return 0;
36
37 int childDepth = 0;
38 for(Node* child : root->children){
39 childDepth = max(childDepth, maxDepth(child));
40 }
41 return 1+childDepth;
42 }
43};
44
45/**
46Solution
47Tree definition
48
49First of all, please refer to this article for the solution in case of binary tree.
50https://leetcode.com/articles/maximum-depth-of-binary-tree/ offers the same ideas with a bit of generalisation.
51**/
52
53/**
54Approach 1: Recursion
55Algorithm
56
57The intuitive approach is to solve the problem by recursion.
58Here we demonstrate an example with the DFS (Depth First Search) strategy.
59**/
60/*
61// Definition for a Node.
62class Node {
63public:
64 int val;
65 vector<Node*> children;
66
67 Node() {}
68
69 Node(int _val, vector<Node*> _children) {
70 val = _val;
71 children = _children;
72 }
73};
74*/
75
76//Your runtime beats 67.95 % of cpp submissions.
77class Solution {
78public:
79 int maxDepth(Node* root) {
80 if(root==NULL){
81 return 0;
82 }else if(root->children.empty()){
83 return 1;
84 }else{
85 int childDepth = 0;
86 for(Node* child : root->children){
87 childDepth = max(childDepth, maxDepth(child));
88 }
89 return 1+childDepth;
90 }
91 }
92};
93/**
94Complexity analysis
95
96Time complexity : we visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes.
97
98Space complexity : in the worst case, the tree is completely unbalanced,
99e.g. each node has only one child node, the recursion call would occur N times (the height of the tree),
100therefore the storage to keep the call stack would be O(N).
101But in the best case (the tree is completely balanced), the height of the tree would be log(N).
102Therefore, the space complexity in this case would be O(log(N)).
103**/
104
105/**
106Approach 2: Iteration
107We could also convert the above recursion into iteration, with the help of stack.
108
109The idea is to visit each node with the DFS strategy, while updating the max depth at each visit.
110
111So we start from a stack which contains the root node and the corresponding depth which is 1.
112Then we proceed to the iterations: pop the current node out of the stack and push the child nodes.
113The depth is updated at each step.
114**/
115
116/*
117// Definition for a Node.
118class Node {
119public:
120 int val;
121 vector<Node*> children;
122
123 Node() {}
124
125 Node(int _val, vector<Node*> _children) {
126 val = _val;
127 children = _children;
128 }
129};
130*/
131
132//Your runtime beats 29.52 % of cpp submissions.
133class Solution {
134public:
135 int maxDepth(Node* root) {
136 stack<pair<Node*, int> > stk;
137 int depth = 0;
138
139 if(root!=NULL)
140 stk.push(make_pair(root, 1));
141
142 while(!stk.empty()){
143 pair<Node*, int> p = stk.top();
144 stk.pop();
145
146 Node* node = p.first;
147 int currentDepth = p.second;
148 depth = max(depth, currentDepth);
149
150 for(Node* child : node->children){
151 stk.push(make_pair(child, currentDepth+1));
152 }
153
154 }
155
156 return depth;
157 }
158};
159
160/**
161Complexity analysis
162
163Time complexity : O(N).
164
165Space complexity : O(N).
166**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.