题解 | #求二叉树的层序遍历#

算法思路

要对二叉树做层序遍历，那么要先能够知道当前层有哪些元素，然后按顺序从左往右遍历，这里最容易想到的就是用队列来存储了，队列的FIFO特性保证遍历顺序；遍历过程中保存好当前层遍历结果以及下一层的元素，然后递归直到二叉树遍历完；

算法实现

public class Solution {
    private static final Queue<TreeNode> curLevelNodes = new ArrayDeque<>();
    private static final ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (root != null) {
            curLevelNodes.add(root);
        }
        levelOrder(curLevelNodes);
        return result;
    }

    private void levelOrder(Queue<TreeNode> curLevelNodes) {
        if (curLevelNodes.isEmpty()) {
            return;
        }
        ArrayList<Integer> levelResult = new ArrayList<>();
        Queue<TreeNode> nextLevelNodes = new ArrayDeque<>();
        // 层序遍历
        TreeNode headNode;
        while ((headNode = curLevelNodes.poll()) != null) {
            levelResult.add(headNode.val);
            if (headNode.left != null) {
                nextLevelNodes.offer(headNode.left);
            }
            if (headNode.right != null) {
                nextLevelNodes.offer(headNode.right);
            }
        }
        // 保存层序遍历结果以及下一层节点
        result.add(levelResult);
        curLevelNodes.addAll(nextLevelNodes);
        levelOrder(curLevelNodes);
    }
}