算法
时间复杂度: 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);
TreeNode *last = root;
TreeNode *cur = root;
vector<int> levelArr;
while (!queue0.empty()) {
TreeNode *node = queue0.front();
queue0.pop();
levelArr.push_back(node->val);
if (node->left) {
queue0.push(node->left);
cur = node->left;
}
if (node->right) {
queue0.push(node->right);
cur = node->right;
}
if (node == last) {
// 如果没有使用move,那么复制levelArr,空间复杂度: O(1) -> O(n)
res.push_back(move(levelArr));
levelArr.clear();
last = cur;
}
}
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);
TreeNode last = root;
TreeNode cur = root;
List<Integer> levelArr = new ArrayList<>();
while (!queue0.isEmpty()) {
TreeNode node = queue0.poll();
levelArr.add(node.val);
if (node.left != null) {
queue0.add(node.left);
cur = node.left;
}
if (node.right != null) {
queue0.add(node.right);
cur = node.right;
}
if (node == last) {
res.add(levelArr);
levelArr = new ArrayList<>();
last = cur;
}
}
return res;
}
}
Python3代码
from collections import deque
class Solution(object):
def printFromTopToBottom(self, root):
res = []
if not root:
return res
queue0 = deque()
queue0.append(root)
last = root
cur = root
levelArr = []
while queue0:
node = queue0.popleft()
levelArr.append(node.val)
if node.left:
queue0.append(node.left)
cur = node.left
if node.right:
queue0.append(node.right)
cur = node.right
if node == last:
res.append(levelArr)
levelArr = []
last = cur
return res
空间复杂度是存储所有变量耗费的空间,某一个变量不同时存在所有数据结构中,这能退出空间复杂度是1 ,我觉得不太对