LeetCode.102.Binary Tree Level Order Traversal 二叉树的层次遍历

题目描述

102 Binary Tree Level Order Traversal
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

---

相似题目

LeetCode.102.Binary Tree Level Order Traversal 二叉树的层次遍历
LeetCode.107.Binary Tree Level Order Traversal II 二叉树自底向上层次遍历
103 Binary Tree Zigzag Level Order Traversal
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

---

解题过程

2020.05 根据每层结点个数遍历一层

利用队列做层次遍历，每次先获取当前 queue 的 size，则此时队列的长度一定就是当前层的结点个数，然后一次性取出 size 个结点遍历，完成一层遍历。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV202005 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (null == root) {
            return new ArrayList<>(new ArrayList<>());
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int levelCount = queue.size();
            List<Integer> levelList = new ArrayList<>();
            // 遍历当前层
            for (int i = 0; i < levelCount; i++) {
                TreeNode treeNode = queue.poll();
                levelList.add(treeNode.val);
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
            }
            // 遍历完一层，加入结果list
            res.add(levelList);
        }
        return res;
    }
}

2020.03 每层后加入分隔结点

层次遍历，或者叫 宽度优先搜索BFS， 不同的是需要找到不同层之间的分隔点，以便放到二位数组中。
每一层开始遍历的时候，当前队列中的元素个数肯定是这层的元素数，官方题解是利用这一点儿来区分层次的。
我是遍历完每一层后，在queue中放入一个标志位 flagNode ，下次再遇到这个标志位就说明当前层的结点遍历完了。

private static class SolutionV202001 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (null == root) {
            return Collections.emptyList();
        }
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> levelList = new ArrayList<>();

        // 层次间隔标识
        TreeNode flagNode = new TreeNode(0);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(flagNode);
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            if (treeNode == flagNode) {
                resultList.add(levelList);
                levelList = new ArrayList<>();
                if (queue.isEmpty()) {
                    break;
                }
                queue.offer(flagNode);
            } else {
                if (null != treeNode.left) {
                    queue.offer(treeNode.left);
                }
                if (null != treeNode.right) {
                    queue.offer(treeNode.right);
                }
                levelList.add(treeNode.val);
            }
        }
        return resultList;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_102_BinaryTreeLevelOrderTraversal.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_102_BinaryTreeLevelOrderTraversal.java

---