N-ary Tree

Binary Tree 때 배웠던 순회 중 In-order traverse(중위 순회)에 대한 정의는 없다.

(1) Preorder Traversal: A->B->C->E->F->D->G
(2) Postorder Traversal: B->E->F->C->G->D->A
(3) Level-order Traversal: A->B->C->D->E->F->G

Preorder Iteration

public List<Integer> preorder(Node root) {
	LinkedList<Node> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
		Node node = stack.pollLast();
		output.add(node.val);
		Collections.reverse(node.children);
		for (Node item : node.children) {
			stack.add(item);
		}
	}
	return output;
}

루트부터 시작하여 각 반복마다 현재 노드를 스택에서 팝(pop)하고 자식 노드를 푸시(push)한다. 구현된 전략에서는 노드를 Top->Bottom, Left->Right 순서로 출력 리스트에 푸시하는데, 이는 자연스럽게 전위 순회(preorder traversal)를 재현합니다.