时间戳

首页 > 解决方案 > 数据结构在 N 叉树的每一层都获得最大值

java - 数据结构在 N 叉树的每一层都获得最大值

问题描述

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

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

我的节点将如下所示： public class Node {

public int val;
public List<Node> children;


public Node() {
    
}

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

我尝试通过每个级别的递归获取元素并找到最大值但无法这样做。

标签： javatreerecursive-datastructuresn-ary-tree

解决方案

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

  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 demo

这个实现有两个很好的属性：

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

稍加努力，我们甚至可以使算法与 generic 一起工作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 demo

推荐阅读