【LeetCode-简单题】589. N 叉树的前序遍历

题目

方法一：单循环栈做法

关键在于子节点的入栈顺序，决定了子节点的出栈顺序，
因为是前序遍历 所以压栈顺序先让右边的入栈 依次往左 这样左边的节点会在栈顶 这样下次优先出栈的是左边的元素 满足前序遍历

 for(int i = root.children.size()-1 ; i>=0 ;i--)
                stack.push(root.children.get(i));
1
2

class Solution {
    public List<Integer> preorder(Node root) {
        if(root==null) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        Deque<Node> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            root  = stack.pop();
            res.add(root.val);

            //因为是前序遍历  所以压栈顺序先让右边的入栈  依次往左  这样左边的节点会在栈顶 这样下次优先出栈的是左边的元素 满足前序遍历
            for(int i = root.children.size()-1 ; i>=0 ;i--)
                stack.push(root.children.get(i));
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：递归

原理和二叉树的前序遍历一样 相当于把左右孩子 改成孩子集合了 孩子变多了而已，核心还是 根左右（先跟 再左孩子 在右孩子）

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) return;
        res.add(root.val);//前
        for(Node node : root.children)//中中中中中
        dfs(node);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13