【数据结构和算法】BFS和DFS两种方式解决

按之字形顺序打印二叉树

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

BFS打印

二叉树的的层次遍历就是一层一层的遍历,也就是我们俗称的BFS(宽度优先搜索算法(又称广度优先搜索)),之前在373,数据结构-6,树 中讲过树的宽度优先搜索,最简单的方式就是使用队列。但这题打印的时候多了一个条件,就是不能一直从一个方向打印,要先从左边打印然后再从右边打印……,就这样交替进行,所以这里要有个变量来判断是从左往右还是从右往左打印,代码比较简单,我们来看下。

import java.util.ArrayList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.Queue;
import java.util.LinkedList;

public class Solution {

    public ArrayList<ArrayList<Integer>> Print(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();
            //遍历这一行的所有节点
            for (int i = 0; i < count; i++) {
                //poll移除队列头部元素(队列在头部移除,尾部添加)
                TreeNode node = queue.poll();
                //判断是从左往右打印还是从右往左打印。
                if (leftToRight) {
                    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.add(level);
            leftToRight = !leftToRight;
        }
        return res;
    }

}

当然我们还可以根据每一层是第几层来判断,如果根节点是第1层的话,那么我们在层数是奇数的时候从左往右打印,如果层数是偶数的时候从右往左打印。在前面我们讲队列的时候359,数据结构-3,队列 我们讲到了双端队列,就是一个可以在两边同时添加和删除的队列。这里我们使用上面两种方式的结合,来看下代码。

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        //双端队列,两边都可以操作
        Deque<TreeNode> deque = new LinkedList<>();
        //添加到队列的头
        deque.addFirst(root);
        while (!deque.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<>();
            //统计这一行有多少个节点
            int count = deque.size();
            //遍历这一行的所有节点
            TreeNode cur;
            for (int i = 0; i < count; i++) {
                if (res.size() % 2 == 1) {
                    //从左边往右边打印
                    //移除队列头部的元素,如果子节点不为空加入到队列的尾部
                    cur = deque.removeFirst();
                    if (cur.right != null)
                        deque.addLast(cur.right);
                    if (cur.left != null)
                        deque.addLast(cur.left);
                } else {
                    //从右边往左边打印
                    //移除队列尾部的元素,如果子节点不为空加入到队列的头部
                    cur = deque.removeLast();
                    if (cur.left != null)
                        deque.addFirst(cur.left);
                    if (cur.right != null)
                        deque.addFirst(cur.right);
                }
                level.add(cur.val);
            }
            res.add(level);
        }
        return res;
    }

}

DFS打印

这题除了使用BFS以外,我们还可以使用DFS。但这里我们要有个判断,如果走到下一层的时候集合没有创建,我们要先创建下一层的集合,代码也很简单,我们来看下。

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {

    public ArrayList<ArrayList<Integer>> Print(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);
    }

}

截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

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

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

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

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

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 10:16
点赞 评论 收藏
转发
头像
2022-12-10 09:46
宁夏大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
5 1 评论
分享

全站热榜

正在热议