【数据结构和算法】BFS和DFS两种方式实现

二叉树的之字形层序遍历

http://www.nowcoder.com/questionTerminal/47e1687126fa461e8a3aff8632aa5559

1,BFS打印

二叉树的BFS打印,就是一层一层的往下打印,就像下面这样
image.png
具体可以看下373,数据结构-6,树,这里介绍了递归和非递归的解法。非递归的代码如下

    public static void levelOrder(TreeNode tree) {
        if (tree == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(tree);//相当于把数据加入到队列尾部
        while (!queue.isEmpty()) {
            //poll方法相当于移除队列头部的元素
            TreeNode node = queue.poll();
            System.out.println(node.val);
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }

因为上面每次都是从左边开始打印,但这题要求的是先从左边,下一层从右边,在下一次从左边……左右交替的。我们可以使用一个变量leftToRight,如果是true就表示从左边开始打印,否则就从右边开始打印,只需要把上面代码修改下即可,来看下

    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        //创建队列,保存节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);//先把节点加入到队列中
        boolean leftToRight = true;//第一步先从左边开始打印
        while (!queue.isEmpty()) {
            //记录每层节点的值
            ArrayList<Integer> level = new ArrayList<>();
            //统计这一层有多少个节点
            int count = queue.size();
            //遍历这一层的所有节点,把他们全部从队列中移出来,顺便
            //把他们的值加入到集合level中,接着再把他们的子节点(如果有)
            //加入到队列中
            for (int i = 0; i < count; i++) {
                //poll移除队列头部元素(队列在头部移除,尾部添加)
                TreeNode node = queue.poll();
                //判断是从左往右打印还是从右往左打印。
                if (leftToRight) {
                    //如果从左边打印,直接把访问的节点值加入到列表level的末尾即可
                    level.add(node.val);
                } else {
                    //如果是从右边开始打印,每次要把访问的节点值
                    //加入到列表的最前面
                    level.add(0, node.val);
                }
                //左右子节点如果不为空会被加入到队列中
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            //把这一层的节点值加入到集合res中
            res.add(level);
            //改变下次访问的方向
            leftToRight = !leftToRight;
        }
        return res;
    }

2,DFS打印

这题除了使用BFS以外,还可以使用DFS,也可以参照373,数据结构-6,树中二叉树的BFS遍历的递归解法,稍作修改。但这里要有个判断,如果走到下一层的时候集合没有创建,要先创建下一层的集合,代码也很简单,我们来看下。

    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        travel(root, res, 0);
        return res;
    }

    private void travel(TreeNode cur, ArrayList<ArrayList<Integer>> res, int level) {
        if (cur == null)
            return;
        //如果res.size() <= level说明下一层的集合还没创建,所以要先创建下一层的集合
        if (res.size() <= level) {
            ArrayList<Integer> newLevel = new ArrayList<>();
            res.add(newLevel);
        }
        //遍历到第几层我们就操作第几层的数据
        List<Integer> list = res.get(level);
        //这里默认根节点是第0层,偶数层相当于从左往右遍历,
        // 所以要添加到集合的末尾,如果是奇数层相当于从右往左遍历,
        // 要把数据添加到集合的开头
        if (level % 2 == 0)
            list.add(cur.val);
        else
            list.add(0, cur.val);
        //分别遍历左右两个子节点,到下一层了,所以层数要加1
        travel(cur.left, res, level + 1);
        travel(cur.right, res, level + 1);
    }

我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的《牛客博客》查看更多的详细题解

数据结构和算法 文章被收录于专栏

专注于算法题的讲解,包含常见数据结构,排序,查找,动态规划,回溯算法,贪心算法,双指针,BFS和DFS等等

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-02 00:03
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
6 收藏 评论
分享

全站热榜

正在热议