「栈模拟迭代」—递归算法优化

模拟系统执行「递归」的过程

具体应用：

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

递归做法:

class DFS{
    public List<Integer> preorder(Node root){
        List<Integer> res = new ArrayList<>();
        dfs(root,res);
        return res;
    }

    public void dfs(Node root,List<Integer> res){
        if(null == root) return;
        //前序遍历位置
        res.add(root.val);
        List<Node> children = root.children;
        for(Node child: children){
            dfs(child,res);
        }
    }
}

迭代做法

class Solution{
    public List<Integer> preorder(Node root){
        //这是结果数组
        List<Integer> res = new ArrayList<>();
        //判空
        if(null == root) return res;
        //栈，利用栈模拟递归
        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);
        while(!stack.isEmpty()){
            //出栈，拿的是栈顶的
            Node pop = stack.pop();
            if(pop == null) continue;
            //将当前遍历的节点的值 添加到结果数组中
            res.add(pop.val);
            //当前节点的孩子节点
            List<Node> children = pop.children;
            //将每个孩子节点，压入栈中，进行下一次遍历
            for(int i = children.size()-1;i>=0;i--){
                //   ？问：为什么这里要倒序遍历压栈
                //   因为是前序遍历，意味着孩子节点要从左往右遍历，如4的孩子节点{1,2,3}，前序遍历应该是{4,1,2,3}，倒序压栈后栈顶就是1了
                stack.push(children.get(i));
            }
        }
        return res;
    }
}