从上到下打印二叉树(Java)

淩亂°似流年 2022-05-14 12:06 231阅读 0赞

**题目：**从上往下打印出二叉树的每个节点，同层节点从左至右打印，（上到下&左到右）。。

**借助辅助队列实现二叉树的层次遍历**

不难看出这是二叉树的遍历，但却不是我们常用的前序、中序、后续遍历，这是一种按层遍历，同一层的结点从左到右打印；

先打印根节点----需要将该结点得到字结点保存到某个容器中；

**例如：**

![70][]

*  先打印根节点 8 ，将子节点 6、10保存到容器（6，10）中；
 *  下一个打印 6（将6从容器中拿出来），将其子节点5、7保存到容器（10，5，7）中；
 *  下一个打印10（将10从容器中拿出来），将其子节点9、11保存到容器（5，7，9，11）中；

**综上 ，容器中的元素 ：先进先出，所以该容器是一个队列；**

**实现打印操作：**每次打印一个结点，如果该结点有子节点，将其子节点放到队列末尾；从队头取出最早进入的元素，继续打印 重复前面的操作，直到队列为空，打印结束。。（**如何实现队列：****S**TL 实现的deque 队列（两边都可以进出的队列）。。）

**扩展：广度遍历有向图。。**。

**代码如下：**

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.Queue;
    /**
    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<Integer>();
            if(root == null){
                return result;
            }
    
            Queue<TreeNode> q = new LinkedList<TreeNode>();
    
            q.add(root);        
            while(!q.isEmpty()){
                TreeNode tmp = q.remove();
                result.add(tmp.val);
                if(tmp.left != null){
                    q.add(tmp.left);
                }
    
                if(tmp.right != null){
                    q.add(tmp.right);
    
                }
            }
            
            return result;
        }
    }

[70]: /images/20220514/3dfefa7bb984482ea26a86e438dddac5.png