算法
时间复杂度: O(n)
空间复杂度: O(1)
因为一个数据不会在一个queue0、levelArr、res中同时存在,所以额外空间复杂度是O(1)
。
C++代码
class Solution {
public:
static vector<vector<int>> printFromTopToBottom(TreeNode *root) {
vector<vector<int>> res;
if (root == NULL) {
return res;
}
queue<TreeNode *> queue0;
queue0.push(root);
while (!queue0.empty()) {
const int levelSize = static_cast<int>(queue0.size());
vector<int> levelArr(levelSize);
for (int i = 0; i < levelSize; ++i) {
TreeNode *node = queue0.front();
queue0.pop();
levelArr[i] = node->val;
if (node->left) {
queue0.push(node->left);
}
if (node->right) {
queue0.push(node->right);
}
}
// 如果没有使用move,那么复制levelArr,空间复杂度: O(1) -> O(n)
res.push_back(move(levelArr));
}
return res;
}
};
Java代码
class Solution {
public static List<List<Integer>> printFromTopToBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue0 = new LinkedList<>();
queue0.add(root);
while (!queue0.isEmpty()) {
final int levelSize = queue0.size();
List<Integer> levelArr = new ArrayList<>(levelSize);
for (int i = 0; i < levelSize; ++i) {
TreeNode node = queue0.poll();
levelArr.add(node.val);
if (node.left != null) {
queue0.add(node.left);
}
if (node.right != null) {
queue0.add(node.right);
}
}
res.add(levelArr);
}
return res;
}
}
Python3代码
from collections import deque
class Solution(object):
def printFromTopToBottom(self, root):
res = []
if root is None:
return res
queue0 = deque()
queue0.append(root)
while queue0:
levelSize = len(queue0)
levelArr = []
for i in range(levelSize):
node = queue0.popleft()
levelArr.append(node.val)
if node.left is not None:
queue0.append(node.left)
if node.right is not None:
queue0.append(node.right)
res.append(levelArr)
return res