算法：二叉树的层序遍历

要求

例如：以下二叉树按4 2 7 1 3 6 9顺序输出，一层一层输出。

     4
   /   \
  2     7
 / \   / \
1   3 6   9

广度优先搜索

根节点先入队列，出队列后将左右节点再加入队列中。

public List<Integer> bfs(Node root) {
    if (root == null)
        return null;
    List<Integer> list = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        list.add(node.id);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    return list;
}

深度优先搜索

定义List<List<Integet>>第一层List存储层数，第二层List<Integer>存储每层的元素。

private List<List<Integer>> levelList = new ArrayList<>();

public void bfsRecursion(Node root, int level) {
    if (root == null) {
        return;
    }
    if (level >= levelList.size()) {
        levelList.add(new ArrayList<>());
    }
    levelList.get(level).add(root.id);
    bfsRecursion(root.left, level + 1);
    bfsRecursion(root.right, level + 1);
}

完整代码

public class TreeBFSPrint {

    public static void main(String[] args) {
        TreeBFSPrint tree = new TreeBFSPrint();

        int[] arr = {4, 2, 7, 1, 3, 6, 9};
        for (int i : arr) {
            Node node = new Node(i);
            tree.add(node);
        }

        System.out.println(tree.root.id);
//        System.out.println(tree.bfs(tree.root));
        tree.bfsRecursion(tree.root, 0);
        System.out.println(tree.levelList);

    }

    public Node root;

    public List<Integer> bfs(Node root) {
        if (root == null)
            return null;
        List<Integer> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            list.add(node.id);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return list;
    }

    private List<List<Integer>> levelList = new ArrayList<>();

    public void bfsRecursion(Node root, int level) {
        if (root == null) {
            return;
        }
        if (level >= levelList.size()) {
            levelList.add(new ArrayList<>());
        }
        levelList.get(level).add(root.id);
        bfsRecursion(root.left, level + 1);
        bfsRecursion(root.right, level + 1);
    }

    public void add(Node node) {
        root = add(root, node);
    }

    public Node add(Node rootNode, Node node) {
        if (rootNode == null) {
            return node;
        }
        if (rootNode.id > node.id) {
            rootNode.left = add(rootNode.left, node);
        } else {
            rootNode.right = add(rootNode.right, node);
        }
        return rootNode;
    }

    private static class Node {
        public int id;
        public Node left;
        public Node right;

        public Node(int id) {
            this.id = id;
        }
    }

}