首页 > 试题广场 >

从上往下打印二叉树

[编程题]从上往下打印二叉树
  • 热度指数:701209 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
不分行从上往下打印出二叉树的每个节点,同层节点从左至右打印。例如输入{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,点此查看相关信息
使用一个动态数组
1.判断是root是否为空,返回空队列。
2.如果不为空先输入根节点。
3.判断ArrayList里面是否为空不为空,则弹出数组的头节点,并判断有没有左右子树
4.有左右子树则添加到ArrayList的尾部。直到ArrayList为空。
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<TreeNode> arrayList = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        arrayList.add(root);
        if(root==null)
            return list;
        while(arrayList.size()!=0) {
        	TreeNode treeNode = arrayList.remove(0);
        	if(treeNode.left!=null) {
        		arrayList.add(treeNode.left);
        	}
        	if(treeNode.right!=null) {
        		arrayList.add(treeNode.right);
        	}
        	list.add(treeNode.val);
        }
    return list;    
    }
}

发表于 2019-08-28 23:02:45 回复(0)
更多回答

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 回复(18)
/**
思路是用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 回复(54)
借助队列实现
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)
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)
这不就是二叉树的层次遍历么,借助一个队列就可以了。
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, 借助一个队列就可以实现
# -*- 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)
/*
从上往下打印二叉树

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

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)
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)
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)
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)