[编程题]从上往下打印二叉树
• 热度指数：592408 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

```class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
if(root==NULL)
return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
res.push_back(q.front()->val);
if(q.front()->left!=NULL)
q.push(q.front()->left);
if(q.front()->right!=NULL)
q.push(q.front()->right);
q.pop();
}
return res;
}
};```

```/**

*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
ArrayList<TreeNode> queue = new ArrayList<>();
if (root == null) {
return list;
}
while (queue.size() != 0) {
TreeNode temp = queue.remove(0);
if (temp.left != null){
}
if (temp.right != null) {
}
}
return list;
}
}```

python solution easy to understand:

```def PrintFromTopToBottom(self, root):
if not root:
return []
currentStack = [root]
res = []
while currentStack:
nextStack = []
for i in currentStack:
if i.left: nextStack.append(i.left)
if i.right: nextStack.append(i.right)
res.append(i.val)
currentStack = nextStack
return res```

java版本：
```public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root==null){
return list;
}
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
}
return list;
}
}```

bfs

```class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode *rt) {
queue<TreeNode*> q;
q.push(rt);
vector<int> r;
while(!q.empty()){
rt = q.front(); q.pop();
if(!rt) continue;
r.push_back(rt -> val);
q.push(rt -> left);
q.push(rt -> right);
}
return r;
}
};```

```# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if not root:
return []
queue = []
result = []

queue.append(root)
while len(queue) > 0:
node = queue.pop(0)
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return result
```

```public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<TreeNode>  listNode=new ArrayList<TreeNode> ();
ArrayList<Integer>  listVal=new ArrayList<Integer> ();
if(root==null)
return listVal;
for(int i=0;i<listNode.size();i++){
TreeNode node=  listNode.get(i);
if(node.left!=null){
}
if(node.right!=null){
}

}

return listVal;
}
}```

```class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode *root) {
vector<int> res;
vector<TreeNode *> array;
if(root == NULL) return res;
array.push_back(root);
int p = 0;
while(p < array.size()){
TreeNode * temp = array[p++];
if(temp->left) array.push_back(temp->left);
if(temp->right) array.push_back(temp->right);
res.push_back(temp->val);
}
return res;
}
};```

1、将第一个元素加入队列
2、队列不为空时取队首元素
3、将下一层元素加入队尾
4、调到第二步，直到队列为空
```/*
struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) :             val(x), left(NULL), right(NULL) {     }
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> result;
if(NULL == root)
return result;

queue<TreeNode* > q;
q.push(root);
while(!q.empty())
{
TreeNode* temp = q.front();
q.pop();
result.push_back(temp->val);
if(NULL != temp->left)
q.push(temp->left);
if(NULL != temp->right)
q.push(temp->right);
}
return result;
}
}; ```

``````//树的广度优先遍历
function PrintFromTopToBottom(root)
{
var nodes = [];
var leafs = [];
if(!root){
return false;
}
nodes.push(root);
while(nodes && nodes.length>0){
var node = nodes.shift();
leafs.push(node.val)
if(node.left){
nodes.push(node.left)
}
if(node.right){
nodes.push(node.right)
}
}
return leafs;
}
``````

``````class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> v;
if(root == NULL) return v;
queue<TreeNode*> q; q.push(root);
while(!q.empty()){
TreeNode* tmp = q.front(); q.pop();
v.push_back(tmp->val);
if(tmp->left != NULL) q.push(tmp->left);
if(tmp->right != NULL) q.push(tmp->right);
}
return v;
}
};
``````

python：使用两个数组，ls存放节点，ls相当于队列， 把每一层的节点都放进去，开始 就是循环节点的左右子节点，然后放在队列 后面，result存放节点的值用于最后返回打印
```class Solution:
def PrintFromTopToBottom(self, root):
if  not root:
return []
# write code here
ls=[root]
result=[]
while len(ls)>0:
node=ls.pop(0)
result.append(node.val)
if node.left!=None:
ls.append(node.left)
if node.right!=None:
ls.append(node.right)
return result
```

```此题是要求将二叉树进行层序遍历，使用队列模拟层序遍历元素的打印顺序，将元素加入到ArrayList。 import java.util.ArrayList; import java.util.LinkedList;

import java.util.Queue;

public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
ArrayList<Integer> res = new ArrayList<Integer>();
while (!arrlist.isEmpty()) {
TreeNode cur = arrlist.poll();
//System.out.println(cur.val);
if (cur.left != null) {
}
if (cur.right != null) {
}
}
return res;
}
}
```

```public class Solution {
//层序遍历
ArrayList<Integer> list=new ArrayList<Integer>();
boolean flag=true;
int i=0;
int count=0;
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<TreeNode> tn=new ArrayList<TreeNode>();//用于保存当前节点的左右子节点
if(root !=null){
while(flag){
if(root.left !=null){
//添加左子树
count++;
}
if(root.right !=null){
//添加右子树
count++;
}
if(i<count){
i++;
root=tn.get(i);//准备添加下一个节点的左右子节点
}else{
flag=false;
}
}
}
for(int j=0;j<tn.size();j++){
}
return list;
}
}
```

``````class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode *tmp = q.front();
res.push_back(tmp->val);
if(tmp->left != NULL) {
q.push(tmp->left);
}
if(tmp->right != NULL) {
q.push(tmp->right);
}
q.pop();
}

return res;

}
};
``````

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/

class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
if(root==NULL)        //需要判断是否为空
return res;
deque<TreeNode*> dequeTreeNode;
dequeTreeNode.push_back(root);
while(dequeTreeNode.size())        //循环终止条件：队列元素全部打印为空
{
TreeNode* pNode= dequeTreeNode.front();   //返回双端队列dequeTreeNode的首元素给pNode
dequeTreeNode.pop_front();             //删除双端队列dequeTreeNode的首元素

res.push_back(pNode->val);        //将此时的dequeTreeNode第一个元素存入到输出容器res中

if(pNode->left)               //若当前结点的左结点不为空，将其左结点存入到双端队列dequeTreeNode中
dequeTreeNode.push_back(pNode->left);
if(pNode->right)
dequeTreeNode.push_back(pNode->right);   ////若当前结点的右结点不为空，将其右结点存入到双端队列dequeTreeNode中
}
return res;
}
};```

```function PrintFromTopToBottom(root)
{
// write code here
var arr = [], arrVal = [];
if(!root){
return arrVal;
}
arr.push(root);

while(arr.length){
var cur = arr.shift();
arrVal.push(cur.val);
if(cur.left){
arr.push(cur.left);
}
if(cur.right){
arr.push(cur.right);
}
}
return arrVal;
}```

```思路1：层次遍历，队列储存左右子节点不为空的指针
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode *root) {
vector<int>result;
queue<TreeNode *> q;
if(root==NULL){
return result;
}
TreeNode *current = root;
q.push(current);
while(!q.empty()){
current = q.front();
q.pop();
result.push_back(current->val);
if(current->left!=NULL){
q.push(current->left);
}
if(current->right!=NULL){
q.push(current->right);
}

}
return result;

}
};

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
void printTree(TreeNode *root,vector<int> & result){
if(root==NULL){
return;
}
result.push_back(root->val);

}
vector<int> PrintFromTopToBottom(TreeNode *root) {
vector<int>result;
queue<TreeNode *> q;
if(root==NULL){
return result;
}
TreeNode *current = root;
result.push_back(current->val);
q.push(current);
while(!q.empty()){
current = q.front();
if(current->left!=NULL){
result.push_back(current->left->val);
if(current->left->left!=NULL||current->left->right!=NULL){
q.push(current->left);
}
}
if(current->right!=NULL){
result.push_back(current->right->val);
if(current->right->left!=NULL||current->right->right!=NULL){
q.push(current->right);
}
}
q.pop();
}
return result;
}
};```

/* struct TreeNode{
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int x)
val(x),left(NULL),right(NULL){
}
}%/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode *root) {
vector<int> result;
queue<TreeNode *>p;
if(root==NULL)
return result;
p.push(root);
while(!p.empty()){
TreeNode * q=p.front();
p.pop();
result.push_back(q->val);
if(q->left!=NULL)
p.push(q->left);

if(q->right!=NULL)
p.push(q->right);
}
return result;
}

};

```//不用队列那么麻烦

import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list=new ArrayList<Integer>();
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if(root!=null)
print(root);
return list;
}
public  void print(TreeNode root){
if(root!=null){
if(root.left!=null)
if(root.right!=null)
print(root.left);
print(root.right);
}
}
}```

1262条回答 115184浏览

# 通过挑战的用户

• 2020-08-07 12:19:01
• 2020-08-07 12:10:26
• 2020-08-07 12:02:13
• 2020-08-07 11:58:35
• 2020-08-07 11:51:00

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题