NC15 求二叉树的层序遍历

拼搏现实的明天。 2022-08-28 05:44 48阅读 0赞

层序遍历一般用队列来做，利用了先进先出的特点。  
根结点先进队，出队的时候读取其左右子结点（如果有的话）进队。然后队列中的结点再出队，并读取其左右子结点入队。

最后按出队的顺序输出即可

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param root TreeNode类 
         * @return int整型ArrayList<ArrayList<>>
         */
        public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        
            // write code here                
            ArrayList<ArrayList<Integer>> list = new ArrayList<>(); // 构造一个空的ArrayList用于存放输出      
            if(root==null) return list; // 根结点为空，直接返回list
            Queue<TreeNode> queue=new LinkedList<>(); // 用一个队列来存结点（先进先出）
            queue.offer(root); // 根结点入队
            // 遍历队列中的结点
            while(!queue.isEmpty()){
        
                int size=queue.size(); // 队列中有几个结点
                ArrayList<Integer> tmp=new ArrayList<>(); // tmp用来存这一层的所有结点值
                // 遍历当前层中的结点
                for(int i=0;i<size;i++){
        
                    TreeNode node=queue.poll(); // 出队
                    if(node.left!=null) queue.offer(node.left);     // 左子结点入队
                    if(node.right!=null) queue.offer(node.right);    // 右子结点入队               
                    tmp.add(node.val); // 取出值放进tmp                
                } 
                // 遍历完一层，加进list
                list.add(tmp);
            }
            return list;        
        }
    }