← 返回 citadel 的题目列表Connect Leaf Nodes of an N-ary Tree Using Next Pointers
类型：online_judge
Problem: Connect Leaf Nodes of an N-ary Tree Using next Pointers
Design a node structure for an N-ary tree:
val: an integer value
children: a list of child nodes; the list order defines the left-to-right DFS order
next: a pointer to another node, initially None
Complete the following tasks:
Compute the sum of all node values in the tree.
Connect all leaf nodes in left-to-right DFS order using the next pointer.
Follow-up: connect the leaf nodes using O(1) extra space. You may temporarily reuse the existing next pointer as a traversal helper, but you may not use an extra array, explicit stack, or queue. The space used by the input tree itself does not count as extra space.
A leaf node is a node whose children list is empty.
Input Format
For judging purposes, the N-ary tree rooted at node 0 is represented as:
n
val_0 val_1 ... val_{n-1}
k_0 child_{0,1} child_{0,2} ... child_{0,k0}
k_1 child_{1,1} ... child_{1,k1}
...
k_{n-1} child_{n-1,1} ... child_{n-1,kn-1}
Where:
n is the number of nodes.
Node i has value val_i.
The next n lines describe the children of each node.
The first integer k_i is the number of children of node i.
It is followed by k_i child indices, in left-to-right DFS order.
The root is always node 0.
Output Format
Print two lines:
The sum of all node values.
The values of leaf nodes after they are connected by next, separated by spaces.
Constraints
1 <= n <= 2 * 10^5
-10^9 <= val_i <= 10^9
The input is guaranteed to be a valid rooted tree with root 0.
The total number of child links is n - 1.
Example
Example 1
Input:
7
1 2 3 4 5 6 7
3 1 2 3
2 4 5
0
1 6
0
0
0
Output:
28
5 6 3 7
Explanation:
The leaves visited by left-to-right DFS are nodes 4, 5, 2, 6, whose values are 5, 6, 3, 7.
Example
Input
1
5
0
Output
5
5