Java教程

二叉树遍历(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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!