二叉树最简单的遍历方式——二叉树的层序遍历

遍历分为深度优先和广度优先，对于二叉树的深度优先遍历我们已经讨论过了常规的，和优化了空间复杂度的,这篇博客我们来讨论二叉树的广度优先遍历，也就是我们常说的层序遍历。 以下图中二叉树为例： 顾名思义二叉树的层序遍历是一层一层的顺序遍历的，上图的二叉树遍历顺序是： A B C D E F G H。 层序遍历大体的遍历方向是由浅到深，由左到右，也就是下图中箭头所示方向： 对于递归遍历和迭代遍历都是关于栈的应用，而层序遍历是关于队列的应用，代码层面的思路是，创建一个队列，根节点先入队列开始循环，每循环又一次，一个节点出队列对该节点进行相应操作，然后让该节点的左右孩子进队列（如果有的话），然后继续循环。

下面是代码实现：

public static void ergodic(TreeNode root){
          
   
        if(root == null){
          
   
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        System.out.print("二叉树的层序遍历： ");
        while (!queue.isEmpty()){
          
   
            TreeNode remove = queue.remove();
            System.out.print((char)remove.val + " ");
            if (remove.left != null){
          
   
                queue.add(remove.left);
            }
            if (remove.right != null){
          
   
                queue.add(remove.right);
            }
        }
    }

用例子中的树测一下

public class Solution {
          
   
    public static TreeNode buildTree() {
          
   

        TreeNode a = new TreeNode(a);
        TreeNode b = new TreeNode(b);
        TreeNode c = new TreeNode(c);
        TreeNode d = new TreeNode(d);
        TreeNode e = new TreeNode(e);
        TreeNode f = new TreeNode(f);
        TreeNode g = new TreeNode(g);
        TreeNode h = new TreeNode(h);

        a.left = b; a.right = c;
        b.left = d; b.right = e;
        c.left = f; c.right = g;
        e.right = h;

        return a;
    }
   public static void ergodic(TreeNode root){
          
   
        if(root == null){
          
   
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        System.out.print("二叉树的层序遍历： ");
        while (!queue.isEmpty()){
          
   
            TreeNode remove = queue.remove();
            System.out.print((char)remove.val + " ");
            if (remove.left != null){
          
   
                queue.add(remove.left);
            }
            if (remove.right != null){
          
   
                queue.add(remove.right);
            }
        }
    }

    public static void main(String[] args) {
          
   
        TreeNode root = buildTree();
        ergodic(root);
    }
}

运行结果如下: