从上往下打印二叉树

分手后的思念是犯贱 2022-03-25 15:29 157阅读 0赞

# [从上往下打印二叉树][Link 1] #

## 题目描述 ##

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：

路线层序遍历，方法广度优先搜索，工具队列

注意点：不同于C/C++，声明队列queue<TreeNode\*> p;  //队列里存放的是地址

** java的queue是接口，需要通过其实现类来完成操作**

![1456741-20180809093802049-1008748512.png][]

注意：

Queue 接口并未定义*阻塞队列的方法*，而这在并发编程中是很常见的。`BlockingQueue` 接口定义了那些等待元素出现或等待队列中有可用空间的方法，这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 `LinkedList`）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

Queue 实现通常未定义 equals 和 hashCode 方法的基于元素的版本，而是从 Object 类继承了基于身份的版本，因为对于具有相同元素但有不同排序属性的队列而言，基于元素的相等性并非总是定义良好的。

![1456741-20180809093913896-1369996921.png][]

1 import java.util.ArrayList;
     2 import java.util.Queue;
     3 import java.util.LinkedList;
     4 /**
     5 public class TreeNode {
     6     int val = 0;
     7     TreeNode left = null;
     8     TreeNode right = null;
     9 
    10     public TreeNode(int val) {
    11         this.val = val;
    12 
    13     }
    14 
    15 }
    16 */
    17 public class Solution {
    18     public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    19           ArrayList<Integer> array=new ArrayList<>();
    20         Queue<TreeNode> p = new LinkedList<TreeNode>();
    21         if (root == null) {
    22             return array;
    23         }
    24       
    25         p.add(root);// 把根节点入队
    26 
    27         while (!p.isEmpty()) {
    28             TreeNode pop1=p.poll();  //每次只会出队一个元素，例如：当前left入队，right入队，left出队，left的俩个孩子入队，然后right出队，right孩子入队...
    31             array.add(pop1.val);
    32 
    33             if (pop1.left != null)
    34             p.add(pop1.left);
    35             if (pop1.right != null)
    36                 p.add(pop1.right);
    37 
    38         }
    39 
    40         return array;
    41 
    42     }
    43 
    44 }

posted @ 2018-08-09 09:44 [Octopus22][] 阅读( ...) 评论( ...) [编辑][Link 2] 收藏

[Link 1]: https://www.cnblogs.com/Octopus-22/p/9447048.html
[1456741-20180809093802049-1008748512.png]: /images/20220325/04654bd0776840dc89b8b609fea1958a.png
[1456741-20180809093913896-1369996921.png]: /images/20220325/c2b6ce7f8e1c4adc87052fa8c2998d8e.png
[Octopus22]: https://www.cnblogs.com/Octopus-22/
[Link 2]: https://i.cnblogs.com/EditPosts.aspx?postid=9447048