面试算法-174-二叉树的层序遍历

题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

解

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        return bfs(root);
    }

    public List<List<Integer>> bfs(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        LinkedList<TreeNode> queue1 = new LinkedList<>();
        LinkedList<TreeNode> queue2 = new LinkedList<>();
        queue1.add(root);
        List<Integer> list = new ArrayList<>();
        while (!queue1.isEmpty()) {
            TreeNode poll = queue1.poll();
            list.add(poll.val);
            if (poll.left != null) {
                queue2.add(poll.left);
            }
            if (poll.right != null) {
                queue2.add(poll.right);
            }

            if (queue1.isEmpty()) {
                result.add(list);
                list = new ArrayList<>();
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return result;
    }
}