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