【每日一题-leetcode】589.N叉树的前序遍历

589.N叉树的前序遍历

589. N叉树的前序遍历

难度简单71

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

1.递归

 //前序遍历  根左右  递归调用即可。
        //先将节点的值存储到linkedList中
    
        LinkedList<Integer> linkedList = null;
        public List<Integer> preorder(Node root) {
            linkedList = new LinkedList();
            return root == null ? new ArrayList() : recur(root);
        }
    
        public LinkedList<Integer> recur(Node root){
            if(root == null)  return null;
            linkedList.add(root.val);
            for(Node node : root.children){
                recur(node);
            }
            return linkedList;
        }

2.栈迭代

//迭代
//前序遍历 根-左-右
//1.将根节点存储到stack中
//2.逆序将子节点添加到栈中 比如 push的顺序为 2 3 4  则输出的顺序为 4 3 2 
public List<Integer> preorder(Node root) {
    if(root == null) return new ArrayList();
    List<Integer> list = new ArrayList();
    Stack<Node> stack = new Stack();

    stack.push(root);

    while(!stack.isEmpty()){
        root = stack.pop();
        list.add(root.val);
        for(int i=root.children.size()-1;i>=0;i--){
            stack.push(root.children.get(i));
        }
    }
    return list;
}