1. 层序遍历

非递归方式

/**
 * 非递归 层序遍历 广度优先算法
 */
public static void bfsOrder2(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    LinkedList<TreeNode> linkedList = new LinkedList<>();
    linkedList.add(treeNode);
    while (!linkedList.isEmpty()) {
        TreeNode node = linkedList.poll();
        System.out.print(node.val);
        if (node.left != null) {
            linkedList.add(node.left);
        }
        if (node.right != null) {
            linkedList.add(node.right);
        }
    }
}

递归方式

/**
 * 层序遍历 
 */
public static void bfsOrder(TreeNode treeNode) {
    int maxDepth = maxDepth(treeNode);
    for (int i = 0; i < maxDepth; i++) {
        printLevel(treeNode, i);
    }
}

/**
 * 打印当前层
 */
private static void printLevel(TreeNode treeNode, int level) {
    if (treeNode == null) {
        return;
    }
    if (level == 0) {
        System.out.print(treeNode.val);
    } else {
        printLevel(treeNode.left, level - 1);
        printLevel(treeNode.right, level - 1);
    }
}

/**
 * 计算树的最大深度
 */
public static int maxDepth(TreeNode treeNode) {
    if (treeNode == null) {
        return 0;
    }
    int maxLeft = maxDepth(treeNode.left);
    int maxRight = maxDepth(treeNode.right);
    return Math.max(maxLeft, maxRight) + 1;
}

2. 实战

题目描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：给定的二叉树是{3,9,20,#,#,15,7},

image

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]

示例1

输入：{1,2}
返回值：[[1],[2]]

示例2

输入：{1,2,3,4,#,#,5}
返回值：[[1],[2,3],[4,5]]

解答

/**
 * 层序遍历
 */
public ArrayList<ArrayList<Object>> levelOrder(TreeNode root) {
    ArrayList<ArrayList<Object>> res = new ArrayList<ArrayList<Object>>();
    if (root == null) {
        return res;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        ArrayList<Object> li = new ArrayList<>();
        while (size-- > 0) {
            TreeNode node = queue.poll();
            if (node == null) {
                continue;
            }
            li.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        res.add(li);
    }
    return res;
}