package LeetCode; import javafx.util.Pair; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class LeetCode102 { /// 102. Binary Tree Level Order Traversal /// https://leetcode.com/problems/binary-tree-level-order-traversal/description/ /// 二叉树的层序遍历 /// 时间复杂度: O(n), n为树的节点个数 /// 空间复杂度: O(n) // Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List> levelOrder(TreeNode root) { ArrayList> res = new ArrayList>(); if(root == null) return res; // 我们使用LinkedList来做为我们的先入先出的队列 LinkedList> queue = new LinkedList>(); queue.addLast(new Pair(root, 0)); while(!queue.isEmpty()){ // 出列，拿到队列的TreeNode和level Pair front = queue.removeFirst(); TreeNode node = front.getKey(); int level = front.getValue(); // 如果level == res.size() --->新的一层--->new 出一个ArrayList() if(level == res.size()) { res.add(new ArrayList()); } assert level < res.size(); res.get(level).add(node.val); if(node.left != null) queue.addLast(new Pair(node.left, level + 1)); if(node.right != null) queue.addLast(new Pair(node.right, level + 1)); } return res; } }