The title

Address:

Analysis of the

Method one: recursion

Code:

class Solution {
     List<Integer> list =new ArrayList<>();
    public List<Integer> preorder(Node root) {
     
        helper(root);
        return list;
    }
    private void helper(Node root){
        if(root == null) return;
        list.add(root.val);
        for(int i=0; i<root.children.size(); i++) helper(root.children.get(i));return; }}Copy the code

Method two: iteration

Since the recursive implementation of n-tree traversal is relatively simple, so we only explain how to use the iterative method to get n-tree traversal.

We use a stack to help us get the prior traversal, and we need to ensure that the node at the top of the stack is the node we are currently traversing. We stack the root node first, because the root node is the first node in the preceding traversal. Then each time we take a node U off the top of the stack, which is the node we are currently traversing, and push all of the children of U back onto the stack. For example, if the child nodes of U are v1, v2, v3 from left to right, the order of pushing on the stack should be V3, v2, v1, so that the next node traversed (i.e., the first child node of U, v1) appears at the top of the stack.

To achieve 1:

class Solution {
    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); }}returnoutput; }}Copy the code

Realization of 2:

public List<Integer> preorder2(Node root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(! stack.isEmpty()) { Node cur = stack.pop();// add the header to the result set
        res.add(cur.val);
        // Push the children of this node from right to left
        for (int i = cur.children.size() - 1; i >= 0; i--) { stack.push(cur.children.get(i)); }}return res;
}
Copy the code