package NTree;

import java.util.ArrayList;
import java.util.List;

/**
* N叉树的前后序遍历和最大深度
*/
public class Ntree {
class Node {
public int val;
public List children;

    public Node() {}

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

public int maxDepth(Node root) {  
    if (root == null) {  
        return 0;  
    } else {  
        int max = 0;  
        for (int i = 0; i < root.children.size(); i++) {  // 遍历子结点，找出子结点中的最大深度  
            max = Math.max(max, maxDepth(root.children.get(i)));  
        }  
        return 1+max;  
    }  
}

List<Integer> pre\_list = new ArrayList<>();  
public List<Integer> preorder(Node root) {  
    if (root == null) {  
        return pre\_list;  
    }  
    pre\_list.add(root.val);  
    for (Node node : root.children) {  
        preorder(node);

    }  
    return pre\_list;  
}

List<Integer> post\_list = new ArrayList<>();  
public List<Integer> postorder(Node root) {  
    if (root == null) {  
        return post\_list;  
    }  
    for (Node node : root.children) {  
        postorder(node);//起到遍历到最后一个元素的作用，存入在最后做

    }  
    post\_list.add(root.val);//遍历到最后一个时候，就会存了，不需要每次都存节点所有子节点，如上种做法那样  
    return post\_list;  
}  

}