Java 二叉树层次遍历

拼搏现实的明天。 2023-02-13 03:42 142阅读 0赞

## Java 二叉树层次遍历 ##

**简介：** 遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有几种情况：DLR（称为先序遍历），LDR（称为中序遍历），LRD （称为后序遍历），层次遍历。

\*\*层次遍历：\*\*按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）。

如图二叉树的层次遍历结果为： 3，9，20，15，7  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5_size_16_color_FFFFFF_t_70_pic_center]  
**代码实现：**

public static void main(String[] args) {
        
        TreeNode root = new TreeNode(3);
        TreeNode n1 = new TreeNode(9);
        TreeNode n2 = new TreeNode(20);
        TreeNode n3 = new TreeNode(15);
        TreeNode n4 = new TreeNode(7);
        root.left = n1;
        root.right = n2;
        n2.left = n3;
        n2.right = n4;
    
        List<List<Integer>> rs = levelOrder(root);
        System.out.println(rs);
    }
    
    public static List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        if (root == null)
            return list;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
    
        while (!deque.isEmpty()) {
        
            int num = deque.size();
            List<Integer> subList = new LinkedList<Integer>();
            for (int i = 0; i < num; i++) {
        
                TreeNode node = deque.removeFirst();
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
                subList.add(node.val);
            }
            list.add(subList);
        }
        return list;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5_size_16_color_FFFFFF_t_70_pic_left]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020060616252810.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5_size_16_color_FFFFFF_t_70_pic_left]: https://img-blog.csdnimg.cn/20200608162826331.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5,size_16,color_FFFFFF,t_70#pic_left