数据结构在N元树的每一级都得到最大值

Question

假设我有一个n元树，如下所示，我需要找到每个级别的最大值，然后返回如下：[8,7,32]。

8
4          3          7
1   4 3    3  5 6 7    12 32 3 1

我的节点将如下所示：公共类节点｛

public int val;
public List<Node> children;

public Node() {

}
public Node(int _val,List<Node> _children) {
val=_val;
children=_children;
}

我试着在每个级别上递归，得到元素并找到最大值，但无法做到

Answer 1

我们可以通过级别顺序遍历/广度优先搜索来获得级别最大值。我们的想法是在一个级别上有一个节点列表/队列。对于该列表中的所有节点，算法做两件事：

1. 它计算该级别上的最大值
2. 它对列表/队列的所有节点进行迭代，获取这些节点的所有子节点，并将它们放在一个新的列表/队列中，然后可以在下一次迭代中进行处理

算法从一个包含(子(树根的列表/队列开始，当列表/队列为空时结束。

这可以用Stream操作很好地表达：

public static List<Integer> getMaxValuePerLevel(Node node) {
final ArrayList<Integer> maxPerLevel = new ArrayList();
maxPerLevel.add(node.getValue());
List<Node> children = node.getChildren();
while (!children.isEmpty()) {
maxPerLevel.add(children.stream()
.mapToInt(Node::getValue)
.max()
.getAsInt());
children = children.stream()
.map(Node::getChildren)
.flatMap(List::stream)
.collect(Collectors.toList());
}
return maxPerLevel;
}

Ideone演示

这个实现有两个不错的特性：

• 它是迭代的，而不是递归的，即算法不受StackOverflowError的约束
• 它具有线性时间和内存复杂性

只要付出一点努力，我们甚至能够使算法与通用Node<T extends Comparable<T>>:一起工作

public static <T extends Comparable<T>> List<T> getMaxValuePerLevel(Node<T> node) {
final ArrayList<T> maxPerLevel = new ArrayList<>();
maxPerLevel.add(node.getValue());
List<Node<T>> children = node.getChildren();
while (!children.isEmpty()) {
final Node<T> defaultNode = children.get(0);
maxPerLevel.add(children.stream()
.map(Node::getValue)
.max(Comparator.naturalOrder())
.orElseGet(defaultNode::getValue));
children = children.stream()
.map(Node::getChildren)
.flatMap(List::stream)
.collect(Collectors.toList());
}
return maxPerLevel;
}

Ideone演示

Answer 2

根节点将成为其级别中的最高节点。对于后续级别，在子节点列表上调用Collections.sort()(或任何其他将对列表排序的比较(，并取最后一个元素(或根据您使用的排序方法具有最高值的元素(。然后遍历刚刚排序的子节点列表，对于每个节点，对其子节点列表应用相同的处理方法。

Answer 3

递归解决方案非常简单。首先创建一个列表来保存结果。然后遍历所有节点：在每个节点上，将节点的值与同一级别的列表中的值进行比较。如果节点的值较大，则替换列表中的值。

class Node {
public int val;
public List<Node> children;
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
public List<Integer> getMaxPerLevel() {
List<Integer> levels = new ArrayList<>();
getMaxPerLevel(0, levels);
return levels;
}
private void getMaxPerLevel(int level, List<Integer> levels) {
if (level >= levels.size()) {
levels.add(level, val);
} else {
levels.set(level, Math.max(val, levels.get(level)));
}
for (Node child : children) {
child.getMaxPerLevel(level + 1, levels);
}
}
}

Answer 4

感谢我使用以下解决方案所做的每一个人：

public List<Integer> levelOrder(Node node){
List<Integer> result = new ArrayList<>();
Queue<Node> queue = new LinkedList<Node>();
queue.add(node);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> currentLevel = new ArrayList<Integer>();
for(int i=0;i<size;i++) {
Node current = queue.remove();
currentLevel.add(current.val);
for(Integer inte:currentLevel) {
System.out.println(inte);
}

if(current.children !=null) {
for(Node node1:current.children)
queue.add(node1);
}
}
result.add(Collections.max(currentLevel));  
}
return result;
}