The title

  • The definition of N fork tree
class Node {
    public int val;
    public List<Node> children;

    public Node(a) {}

    public Node(int _val) {
        val = _val;
    }

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

Train of thought

  • Add the root node first, then the child nodes (in left-to-right order)
  • Reverse stack, resulting in tail insert

Method 1: iteration

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;/ / sentence
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(! stack.isEmpty()) { Node cur = stack.pop(); res.add(cur.val);for (int i = cur.children.size() - 1; i >= 0; i--) {// Push backwards so that pop is in positive order
                stack.push(cur.children.get(i));// Since this is limited to size(), there is no need to worry about adding null nodes}}returnres; }}Copy the code

Method two: recursion

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        dfs(root);
        return res;
    }
    public void dfs(Node root) {
        if (root == null) {// This is a special judgment, not a recursive termination condition
            return;
        }
        res.add(root.val);
        for (Node node : root.children) {// Recursive termination conditions are implicit in thisdfs(node); }}}Copy the code