← 返回 snowflake 的题目列表Prune an N-ary Tree to a Maximum Depth
类型：online_judge
Given a rooted N-ary tree and an integer k:
Return the maximum depth of the tree.
Delete as few nodes as possible so that the remaining tree has maximum depth at most k.
Use the following conventions:
The root has depth 0.
Deleting a node deletes its entire subtree.
Return the minimum number of deleted nodes and the values of the deleted nodes, in any order.
Node values are unique.
Do not use dynamic programming.
Example 1
Tree:
1
├── 2
│ ├── 5
│ └── 6
└── 3
└── 4
k = 1
Maximum depth = 2
The exact minimum depends on the intended deletion semantics. If deleting a node removes its subtree and each chosen deletion counts as one node, deleting 2 and 3 removes all nodes deeper than depth 1 using two deletions, while deleting [5, 6, 4] uses three. Confirm this semantic with the interviewer.
Example 2
Tree:
1
├── 2
│ └── 5
│ └── 7
└── 3
└── 6
k = 2
Maximum depth = 3
Minimum deletion count = 1
One valid answer = [5]
Constraints
Number of nodes n: 1 <= n <= 2 * 10^5
0 <= k <= n - 1
The total number of child edges is n - 1
Design an O(n)-time algorithm using O(h) recursive-stack space, or O(n) explicit-stack space.
Example
Input
7 1
1:2,3
2:5,6
3:4
4:
5:
6:
7:
1
Output
2
2
2 3