二叉树遍历（BFS）

本文主要是介绍二叉树遍历（BFS），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

解体思想：

1. 使用BFS来解；
2. 只使用BFS无法解决之字形的转换，所以需要进行判断：当从右往左打印的时候需要特殊处理：
   2.1 将这一层的节点从queue中poll出来并push到一个临时的stack中，同时将其孩子加入到队列中；
   2.2 使用临时stack中的数据，将其以此pop出来打印即可（因为从queue出来到stack已经实现了翻转）；
3. 注意每一层打印之后输出方向的转换。

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            // list存储最终的结果
            List<List<Integer>> list = new ArrayList<>();
            // 队列存储每一层的节点（从左往右顺序）
            Queue<TreeNode> queue = new LinkedList<>();
            // 标志是打印方向，true表示从左往右
            boolean flag = true;  
            // 添加根节点
            if(root != null) queue.add(root);
            // 标准的BFS遍历开始
            while(!queue.isEmpty()){
                // 当前队列的大小，即当前层的节点个数
                int len = queue.size();
                // 临时集合用于存放当前层的数据
                List<Integer> tem = new ArrayList<>();

                // 从左到右打印，这和普通BFS一样
                if(flag){
                    for(int i=0; i<len; i++){
                        TreeNode node = queue.poll();
                        tem.add(node.val);
                        if (node.left != null) queue.add(node.left);
                        if (node.right != null) queue.add(node.right);
                    }
                }

                // 从右到左
                else{
                    // 使用Deque代替了stack
                    Deque<TreeNode> stack = new LinkedList<>();
                    // 将当前层的节点一次push到stack中，同时将其孩子节点放入queue中（只有在这里加入队列才能保证入队的顺序是从左往右的）
                    for(int i=0; i<len; i++){
                        TreeNode node = queue.poll();
                        if (node.left != null) queue.add(node.left);
                        if (node.right != null) queue.add(node.right);
                        stack.push(node);
                    }
                    // 一次pop出stack中的节点，将数据保存临时集合中
                    for(int j=0; j<len; j++){
                        TreeNode node = stack.pop();
                        tem.add(node.val);
                    }
                }
                // 转换标志（改变打印方向）
                flag = !flag;
                // 保存当前层的数据
                list.add(tem);
            }
            // 返回
            return list;
        }

这篇关于二叉树遍历（BFS）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！