首页 > 试题广场 > 从上往下打印二叉树
[编程题]从上往下打印二叉树
  • 热度指数: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;
    }
};

编辑于 2017-08-17 09:12:19 回复(21)
/**
思路是用arraylist模拟一个队列来存储相应的TreeNode
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<TreeNode> queue = new ArrayList<>();
        if (root == null) {
            return list;
        }
        queue.add(root);
        while (queue.size() != 0) {
            TreeNode temp = queue.remove(0);
            if (temp.left != null){
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
            list.add(temp.val);
        }
        return list;
    }
}

发表于 2016-08-23 11:49:48 回复(51)

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
编辑于 2017-09-11 09:32:18 回复(17)
这不就是二叉树的层次遍历么,借助一个队列就可以了。
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)
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)
实际就是广度优先搜索 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)
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)
广搜的套路就是用一个队列保存将要搜索的这一层的元素,然后逐个搜索;
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)

这是一道树的广度优先遍历的题,建议对这方面知识不明白的朋友先去了解一下广度优先遍历和深度优先遍历的原理。
推荐篇文章,使用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)

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

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:使用两个数组,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)

此题是要求将二叉树进行层序遍历,使用队列模拟层序遍历元素的打印顺序,将元素加入到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)
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)
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)
/*
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)
用队列即可广度优先遍历二叉树

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)
//不用队列那么麻烦

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)