算法
时间复杂度: O(n)
空间复杂度: O(n)
因为一层数据会在nodeVec、levelArr中同时存在,所以额外空间复杂度是O(n)
。
C++代码
class Solution {
public:
static vector<vector<int>> printFromTopToBottom(TreeNode *root) {
vector<vector<int>> res;
if (root == NULL) {
return res;
}
vector<TreeNode *> nodeVec(1, root);
while (!nodeVec.empty()) {
vector<int> levelArr(nodeVec.size());
vector<TreeNode *> nodeVec1;
for (size_t i = 0; i < nodeVec.size(); ++i) {
TreeNode *node = nodeVec[i];
levelArr[i] = node->val;
if (node->left) {
nodeVec1.push_back(node->left);
}
if (node->right) {
nodeVec1.push_back(node->right);
}
}
nodeVec = move(nodeVec1);
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;
}
List<TreeNode> nodeVec = new ArrayList<>(1);
nodeVec.add(root);
while (!nodeVec.isEmpty()) {
List<Integer> levelArr = new ArrayList<>(nodeVec.size());
List<TreeNode> nodeVec1 = new ArrayList<>();
for (TreeNode node : nodeVec) {
levelArr.add(node.val);
if (node.left != null) {
nodeVec1.add(node.left);
}
if (node.right != null) {
nodeVec1.add(node.right);
}
}
res.add(levelArr);
nodeVec = nodeVec1;
}
return res;
}
}
Python3代码
class Solution(object):
def printFromTopToBottom(self, root):
res = []
if not root:
return res
nodeVec = [root]
while nodeVec:
levelArr = []
nodeVec1 = []
for node in nodeVec:
levelArr.append(node.val)
if node.left:
nodeVec1.append(node.left)
if node.right:
nodeVec1.append(node.right)
nodeVec = nodeVec1
res.append(levelArr)
return res