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

具体应用:

给定一个 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;
    }
}

评论