二叉树--按层遍历

今天练习的算法是按层遍历一个二叉树。

题目介绍

我们还是用这张老的二叉树来举例子吧：

二叉树遍历题目.png

按层遍历的意思是从树的跟节点开始，一层层遍历并输出节点的值。输出的结果使用二维的数组存放，我们使用List<List<Integer>>来表示。上图的结果为：
[
[F],
[B,G],
[A,D,I],
[C,E,H]
]

实现思路

老规矩先看图：

二叉树-按层遍历解题思路.png

实现最主要的技巧就是使用队列（Queue），我还是使用递归的思想来分析吧，每次进入递归前带有四个参数orderList、queue、level、preSize。
先稍微分析下四个参数作用吧：

• orderList：结果列表，结构就是和上述结果的结构一致。
• queue：存放节点的队列，满足FIFO原则。
• level：当前递归的层次，主要用来定位存放到orderList的下标。
• preSize：上一层的节点长度，用来确定当此递归需要从queue中取出的元素个数。

基本实现逻辑如下：
1.先从根节点开始，初始化orderList、queue、level、preSize，其中orderList为空，queue中存放root节点，level为0，preSize为1。
2.进入递归方法，首先循环从queue队列中取出preSize数量的节点；然后挨个遍历取出的节点，将节点的值添加到orderList对应的层(level)中；同时将节点的左右子节点均添加到queue队列中，并且记录存放到queue中的节点数量以备下次递归使用；最后根据记录的下一层节点数量判断是否需要继续递归。

核心是要边遍历某一层的时候同时将该层节点的所有节点添加到queue中，并且记录下一层总的节点数，这样才能保证下一层遍历时不会从队列中取到非该层的节点。

实现代码

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class SolutionLevelTraversal {

        public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> orderList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (null != root) {
            int level = 0;
            int size = 1;
            queue.add(root);
            return levelOrder(orderList, queue, level, size);
        }
        return orderList;
    }

    public List<List<Integer>> levelOrder(List<List<Integer>> orderList, Queue<TreeNode> queue, int level, int preSize) {
        List<Integer> leverList = new ArrayList<>();
        int size = 0;
        while (preSize > 0) {
            TreeNode node = queue.remove();
            leverList.add(node.val);
            if (null != node.left) {
                queue.add(node.left);
                size++;
            }
            if (null != node.right) {
                queue.add(node.right);
                size++;
            }
            preSize--;
        }

        orderList.add(leverList);

        if (size > 0) {
            return levelOrder(orderList, queue, ++level, size);
        }
        return orderList;
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms