首页 > 试题广场 >

从上往下打印二叉树

[编程题]从上往下打印二叉树
  • 热度指数：707379 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

数据范围:
0<=节点总数<=1000
-1000<=节点值<=1000
示例1

输入

{8,6,10,#,#,2,1}

输出

[8,6,10,2,1]
示例2

输入

{5,4,#,3,#,2,#,1}

输出

[5,4,3,2,1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
马客(Mark)头像 马客(Mark)
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;
    }
};

发表于 2015-08-23 00:30:10 回复(30)
HelloAndroid头像 HelloAndroid
这不就是二叉树的层次遍历么，借助一个队列就可以了。
java版本： 
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root==null){
            return list;
        }
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		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);
			}
			list.add(treeNode.val);
		}
		return list;
    }
}

发表于 2015-11-13 09:40:16 回复(30)
Python
Yannyezixin头像 Yannyezixin
实际就是广度优先搜索 BFS, 借助一个队列就可以实现 
# -*- 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

发表于 2016-07-25 15:07:04 回复(3)
渡不过己头像 渡不过己
思路还是很清晰的，使用两个队列一个存放节点，一个存放值。先将根节点加入到队列中，然后遍历队列中的元素，遍历过程中，访问该元素的左右节点，再将左右子节点加入到队列中来 
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;
        listNode.add(root);
        listVal.add(root.val);
        for(int i=0;i<listNode.size();i++){
          TreeNode node=  listNode.get(i);
            if(node.left!=null){
                listNode.add(node.left);
                listVal.add(node.left.val);
            }
            if(node.right!=null){
                listNode.add(node.right);
                  listVal.add(node.right.val);
        }
            
        }
        
        return listVal;
    }
}

发表于 2015-09-08 17:16:27 回复(10)
lizo头像 lizo 
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;
    }
};

发表于 2015-08-12 16:30:17 回复(1)
东方小龙2129360头像 东方小龙2129360
广搜的套路就是用一个队列保存将要搜索的这一层的元素，然后逐个搜索；
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;
    }
};

发表于 2018-03-07 22:32:26 回复(4)
dayday_up头像 dayday_up

这是一道树的广度优先遍历的题，建议对这方面知识不明白的朋友先去了解一下广度优先遍历和深度优先遍历的原理。
推荐篇文章，使用js实现的：https://segmentfault.com/a/1190000008954436

//树的广度优先遍历
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;
}
发表于 2017-06-24 11:41:59 回复(1)
C/C++
卷积神经网络哦头像 卷积神经网络哦

经典的宽度优先搜索 队列实现

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;
    }
};
发表于 2018-12-02 16:18:16 回复(0)
Python
人民的名义头像 人民的名义
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

发表于 2017-11-06 21:13:32 回复(1)
Java
624huiguorou头像 624huiguorou
/*
从上往下打印二叉树

层序遍历，用队列实现，非递归

queue用LinkedList来实现
*/ 
import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    //层序遍历，用队列，非递归
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        if(root == null) return resList;
        //queue用LinkedList实现
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            //queue里面没有null
            TreeNode tempNode = queue.poll();
            resList.add(tempNode.val);
            if(tempNode.left != null) queue.add(tempNode.left);
            if(tempNode.right != null) queue.add(tempNode.right);
        }
        return resList;
    }
}


发表于 2021-08-23 16:54:31 回复(1)
Python3
Akshan头像 Akshan 
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        res,queue = [],[]
        if root == None:
            return res
        queue.append(root)
        while  queue:
            node = queue.pop(0)
            res.append(node.val)
            if node.left != None:
                queue.append(node.left)
            if node.right !=None:
                queue.append(node.right)
        return res

编辑于 2021-07-14 10:03:44 回复(0)
Python
SapphireZ头像 SapphireZ 
class Solution:
    def PrintFromTopToBottom(self, root):
        layer_list = [root]
        if root is None:
            return []
        for node in layer_list: # 遍历每一层，元素加到列表末尾
            if node.left:
                layer_list.append(node.left)
            if node.right:
                layer_list.append(node.right)
        return [i.val for i in layer_list]
有比我这更简单的吗？哈哈哈，使了点小聪明，动态改变循环的列表，也达到了队列的效果
发表于 2020-09-25 00:35:42 回复(0)
打工不可能打工的头像 打工不可能打工的 

此题是要求将二叉树进行层序遍历，使用队列模拟层序遍历元素的打印顺序，将元素加入到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>();
        }
        Queue<TreeNode> arrlist = new LinkedList<TreeNode>();
        ArrayList<Integer> res = new ArrayList<Integer>();
        arrlist.add(root);
        while (!arrlist.isEmpty()) {
            TreeNode cur = arrlist.poll();
            //System.out.println(cur.val);
            res.add(cur.val);
            if (cur.left != null) {
                arrlist.add(cur.left);
            }
            if (cur.right != null) {
                arrlist.add(cur.right);
            }
        }
        return res;
    }
}

编辑于 2018-07-13 23:47:04 回复(0)
jiaxx头像 jiaxx 
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){
            tn.add(root);
            while(flag){
                if(root.left !=null){
                    //添加左子树
                    tn.add(root.left );
                    count++;
                }
                if(root.right !=null){
                    //添加右子树
                    tn.add(root.right);
                    count++;
                }
                if(i<count){
                    i++;
                    root=tn.get(i);//准备添加下一个节点的左右子节点
                }else{
                    flag=false;
                }
            }
        }
        for(int j=0;j<tn.size();j++){
            list.add(tn.get(j).val);
        }
        return list;
    }
}

发表于 2018-01-20 10:16:36 回复(0)
C/C++
Jensen头像 Jensen 
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;

    }
};
发表于 2017-12-05 18:30:11 回复(0)
rs勿忘初心头像 rs勿忘初心 
/*
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;
    }
};

发表于 2017-07-26 11:48:46 回复(0)
silver_bullet头像 silver_bullet
用队列即可广度优先遍历二叉树 

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;
}

发表于 2017-03-30 22:42:30 回复(0)
碗碗头像 碗碗 
思路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;

    }
};



思路2： 队列储存左右子节点的子节点不为空的指针


/*
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;
    }
};

编辑于 2015-06-08 07:41:28 回复(0)
小麻雀头像 小麻雀
/* 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;
    }

};

发表于 2015-06-04 11:23:40 回复(0)
LinYu头像 LinYu 
//不用队列那么麻烦

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

编辑于 2016-08-22 16:29:30 回复(14)
提交观点

问题信息

队列 树
难度：
1412条回答 140087浏览

热门推荐

通过挑战的用户

查看代码

相关试题

从上往下打印二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号