java - MINIMAX算法如何从树底向上进行BFS？

Question

每个节点都有一个ArrayList<Node> child 的。

叶子已被评估。我想逐级为叶子以上的所有节点设置值，因此我必须为特定级别上的所有节点设置值以转到其父级并为它们设置值。

换句话说:1假设为级别 X 上的节点设置在为 X-1 级别的节点设置之前

换句话说2:在接近根之前，我需要为 X 级上的所有叶子设置 node.evaluation = 1。

如何做到这一点？我在下面尝试过，但似乎是错误的。我已经尝试了一个星期了。

evaluateTree2(root);
    ....
public void evaluateTree2(Node node){
        for(Node descendant  : node.children) {
            evaluateTree2(descendant);  
            node.evaluation = 1;
            }       
}

Answer 1

您可以使用堆栈和队列。用于从下到上逐级打印节点的伪代码:(请注意，将子节点放入 my_queue 的顺序可能对您的应用程序很重要)。

时间复杂度为 O(n)。堆栈和队列中的插入和弹出都是 O(1)，给定 n 个元素，每个元素有 n 个弹出和插入，总顺序是线性的，即 O(n)。

Stack my_stask
Queue my_queue

insert tree.root into my_queue

while my_queue != empty
  pop Node node from my_queue
  push node.children into my_queue
  push node into my_stask

while my_stask != empty
  pop Node node from my_stask
  print node