剑指 Offer 32 - II. 从上到下打印二叉树 II

剑指 Offer 32 - II. 从上到下打印二叉树 II

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5v22om/

层序遍历

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 使用队列存放节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 存放每一层的遍历结果
        List<List<Integer>> resList = new ArrayList<>();
        // 初使化
        if (root != null) queue.add(root);
        // 如果队列不为空
        while (!queue.isEmpty()) {
            // 存放当前层的遍历结果
            List<Integer> tempList = new ArrayList<>();
            resList.add(tempList);
            // 当前层打印循环，即长度等于队列长度，注意 i 是从大小到
            for (int i = queue.size() - 1; i >= 0; i --) {
                // 拿出队首
                TreeNode node = queue.poll();
                // 将队首的值放入结果集
                tempList.add(node.val);
                // 将队首的左右节点分别入队
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return resList;
    }
}