-1

假设我有一个如下所示的 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;
}

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

4

4 回答 4

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 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

于 2020-08-20T21:45:55.880 回答
0

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

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;
}
于 2020-08-21T23:05:29.887 回答
0

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

于 2020-08-20T21:30:52.500 回答
0

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

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);
        }
    }
}
于 2020-08-20T21:36:11.773 回答