首页 > 试题广场 >

从上往下打印二叉树

[编程题]从上往下打印二叉树

热度指数：701886 时间限制：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，点此查看相关信息

算法知识视频讲解

Java

张道玄

import java.util.*;
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        // 结果集合
        ArrayList<Integer> result = new ArrayList<>();
        // 节点队列 用来实现层序便利
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            // 首先把头结点加入队列
            queue.add(root);
            // 循环便利队列 队列为空说明遍历完毕
            while(!queue.isEmpty()) {
                // 获取队列头结点 并将该节点的val放入结果集合
                TreeNode p = queue.poll();
                result.add(p.val);
                // 将该节点的左右孩子按顺序加入队列尾部
                if (p.left != null) {
                    queue.add(p.left);
                }
                if (p.right != null) {
                    queue.add(p.right);
                }
            }
        }
        return result;
    }
}

层序便利用队列实现

发表于 2023-07-31 01:02:13 回复(0)

Java

里维阿克曼

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null)
            return new ArrayList<>();
        if (root.left == null && root.right == null) {
            res.add(root.val);
            return res;
        }
        ArrayList<TreeNode> temp = new ArrayList<>();
        temp.add(root);
        while (!temp.isEmpty()) {
            ArrayList<TreeNode> temp2 = new ArrayList<>();
            for (TreeNode node : temp) {
                res.add(node.val);
                if (node.left != null)
                    temp2.add(node.left);
                if (node.right != null)
                    temp2.add(node.right);
            }
            temp = temp2;
        }
        return res;
    }
}

发表于 2022-10-09 10:32:51 回复(0)

Java

肥咩咪

import java.util.*;
public class Solution {
    //领导是第一个离职的，大家都排着队离职，从上往下离职，直到所有员工都离职
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(root);//先把领导加入离职队列中
        while(!queue.isEmpty()){
            TreeNode byeNode=queue.poll();//正在离职的人
            int value=byeNode.val;
            list.add(value);//离职后，需要把你的成就留下
            if(byeNode.left!=null){//如果离职的那个人有左膀
                queue.add(byeNode.left);//他的左膀也要排着队离职
            }
            if(byeNode.right!=null){//如果离职的那个人有右臂
                queue.add(byeNode.right);//他的右臂也要排着队离职
            }
        }
        return list;
    }
}

发表于 2022-09-19 22:55:10 回复(0)

Java

牛客嗷嗷

import java.util.*;
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList arr = new ArrayList<>();
        if (root == null)
            return arr;

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            arr.add(node.val);
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
        return arr;
    }
}

发表于 2022-08-16 16:13:46 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.removeFirst();
                res.add(treeNode.val);
                if (treeNode.left != null) {
                    deque.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    deque.add(treeNode.right);
                }
            }
        }
        return res;
    }
}

发表于 2022-06-23 21:56:39 回复(0)

Java

牛客961072936号

import java.util.*;

public class Solution {
    ArrayList<Integer> result = new ArrayList<Integer>();
    
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        if(root==null){
            return new ArrayList<Integer>();
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        dps(stack);
        return result;
    }
    public void dps(Stack<TreeNode> stack) {
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        if(stack.empty()){
            return;
        }
        while(!stack.empty()){
            TreeNode root = stack.pop();
            result.add(root.val);
            if(root.left!=null){
                stack1.push(root.left);
            }
            if(root.right!=null){
                stack1.push(root.right);
            }
        }
        while(!stack1.empty()){
            stack2.push(stack1.pop());//保证顺序入栈
        }
        dps(stack2);
        
    }
}

发表于 2022-06-10 16:12:46 回复(0)

Java

燕大计算机研究僧

就是层次遍历

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer>arrayList=new ArrayList<>();
            if(root==null) return arrayList;
            Queue<TreeNode>queue=new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                int num=queue.size();
                for (int i = 0; i < num; i++) {
                    TreeNode treeNode=queue.poll();
                    arrayList.add(treeNode.val);
                    if(treeNode.left!=null) queue.offer(treeNode.left);
                    if(treeNode.right!=null) queue.offer(treeNode.right);
                }
            }
            return arrayList;       
    }
}

发表于 2022-06-06 14:51:59 回复(0)

Java

txy_钟琛

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
       ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            
            TreeNode cur = queue.poll();
            ans.add(cur.val);
            if (cur.left!=null){
                queue.add(cur.left);
            }
            if (cur.right!=null){
                queue.add(cur.right);
            }
        }
        return ans;
    }
}

发表于 2022-05-26 12:10:35 回复(0)

Java

念您

public class Solution {
    
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {     
        ArrayList<Integer> list = new ArrayList<>(); 
        ArrayList<TreeNode> l = new ArrayList<>(); 
        if(root != null){
            l.add(root);
        }else{
            return list;
        }   
        int i =0;
        while(i < l.size()){
            list.add(l.get(i).val);
            if(l.get(i).left != null){
                l.add(l.get(i).left);                    
            }
            if(l.get(i).right != null){
                l.add(l.get(i).right);
            }
            i++;
        }
        return list; 
    }
}

发表于 2022-05-12 09:29:30 回复(0)

Java

zhenggw

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>(); // 放入遍历二叉树的节点(本质上是维护宽搜)
        if (root != null) {
            queue.add(root);
        }
        // 迭代的过程->宽搜
        while (!queue.isEmpty()) {
            TreeNode node = queue.peek();
            ans.add(node.val); // 将当前节点的val值放入ArrayList中
            // 同层节点从左至右打印
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            queue.poll(); // 当前节点val值已经放入ans中，所以要删去
        }
        return ans;
    }
}

发表于 2022-03-25 11:29:15 回复(0)

Java

总有叼民想害我Y

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();

		if (root == null) {
			return result;
		}

		LinkedList<TreeNode> nexLevel = new LinkedList<>();
		nexLevel.addLast(root);

		while (!nexLevel.isEmpty()) {
			TreeNode current = nexLevel.removeFirst();
			if (current != null) {
				result.add(current.val);
				nexLevel.addLast(current.left);
				nexLevel.addLast(current.right);
			}
		}
		
		return result;
    }
}

发表于 2022-03-15 22:55:26 回复(0)

Java

是小王吖🐅

import java.util.Deque;
import java.util.ArrayDeque;
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
       
        ArrayList<Integer> list=new ArrayList();
         if(root==null) return list;
        Deque<TreeNode> deque=new ArrayDeque();
        deque.offer(root);
        int size=1;
        int nextsize=0;
        TreeNode tmp=null;
        while(!deque.isEmpty()){
            nextsize=0;
            for(int i=0;i<size;i++){
                tmp=deque.poll();
                list.add(tmp.val);
                if(tmp.left!=null){
                    deque.offer(tmp.left);
                    nextsize++;
                }
                if(tmp.right!=null){
                    deque.offer(tmp.right);
                    nextsize++;
                }
            }
            size=nextsize;
        }
        return list;
    }
}

发表于 2021-12-28 20:15:23 回复(0)

Java

愣头bu青

import java.util.ArrayList;
import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(root==null){
            return res;
        }
        queue.add(root);//根节点入队
        while(!queue.isEmpty()){
            //节点出队
            TreeNode node = queue.remove();
            res.add(node.val);
            if(node.left!=null) queue.add(node.left);//节点左子树入队
            if(node.right!=null) queue.add(node.right);//节点右子树入队
        }
        return res;
    }
    
    
}

发表于 2021-11-30 12:45:21 回复(0)

Java

长孙歌澜

创建2个list存放临近2层的数据，来回倒，左脚踩右脚上天那种

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<TreeNode> tmp1 = new ArrayList<>();
    ArrayList<TreeNode> tmp2 = new ArrayList<>();
    tmp1.add(root);
    while (!(tmp1.isEmpty() && tmp2.isEmpty())) {
        for (TreeNode treeNode : tmp1) {
            if (treeNode == null) {
                continue;
            }
            result.add(treeNode.val);
            tmp2.add(treeNode.left);
            tmp2.add(treeNode.right);
        }
        tmp1.clear();
        for (TreeNode treeNode : tmp2) {
            if (treeNode == null) {
                continue;
            }
            result.add(treeNode.val);
            tmp1.add(treeNode.left);
            tmp1.add(treeNode.right);
        }
        tmp2.clear();
    }
    return result;
}

发表于 2021-09-17 09:02:50 回复(0)

Java

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)