【题32 从上到下打印二叉树】

曾经终败给现在 2022-03-10 08:12 194阅读 0赞

【题32 从上到下打印二叉树】  
【题目】从上往下打印出二叉树的每个节点，同层节点从左至右打印。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]【思路如图】如果一个节点有左右子节点，先打印根节点，再将子节点保存，再打印。  
【实现】

import java.util.ArrayList;
    import java.util.LinkedList;
    /**
    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> arr = new ArrayList<Integer>();//数组 最终打印的数组（数组顺序即为最终层次遍历的顺序）
            LinkedList<TreeNode> deque = new LinkedList<TreeNode>();//队列，辅助使用，将节点的左右节点暂存
            //如果根节点为空，则直接返回数组
            if(root == null){
                return arr;
            }
            //如果根节点不为空，将根节点存储进队列
            deque.add(root);
            //如果队列不为空
            while(!deque.isEmpty()){
            //p指向即将出队列的点
                TreeNode p = deque.pop();
                //将出队列的节点的值存入数组arr
                arr.add(p.val);
                //如果节点有左节点，将节点添加到队列
                if(p.left != null){
                    deque.add(p.left);
                }
                //如果有右子节点，添加到队列
                if(p.right != null){
                    deque.add(p.right);
                }
            }
            return arr;
        }
    }

参考：  
1.《剑指offer》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220310/5be2399059144ce2999ef2429dadb900.png