B26 题解 | #求二叉树的层序遍历#

进步感受：

递归的方法，没有什么好讲的，就是前序遍历的变种，只是传了depth的参数。

终于彻底弄懂，队列的层序遍历了！Good job！

下面解题思路分享弄懂过程。

解题思路：队列版本，关键是下面这句，创造了一种特殊的队列循环！

while(!q.isEmpty()) { n=q.size(); for(int i=0;i<n;i++) { q.poll(); q.add()} }

1、 定义队列循用于存入每一层的节点，初始化先存root节点；

2、 通过while嵌套for循环遍历，逐个取出第n层节点值，并新加下一层节点，过程如下：

import java.util.*;

public class Solution {
    /**
     * 层次遍历本质上是一种变种的前序遍历
     * 只是增加了一个depth作为记录，你在哪一层，
     * 在递归的时候，就可以层层递进传递下去
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder2 (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        preOrderTreeNode(root, res, 1);
        return res;
    }

    void preOrderTreeNode(TreeNode root, ArrayList<ArrayList<Integer>> res, int depth) {
        if(root!=null) {
            if(res.size()< depth) {
                res.add(new ArrayList<Integer>());
            }
            res.get(depth-1).add(root.val);
        } else {
            return;
        }
        preOrderTreeNode(root.left, res, depth+1);
        preOrderTreeNode(root.right, res, depth+1);
    }

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>>  res = new ArrayList<ArrayList<Integer>> ();
        if(root == null) {
            return res;
        }
        // 定义队列循存入每一层的节点
        ArrayDeque<TreeNode> q = new ArrayDeque<>();
        // 根节点入队进入第一层遍历
        q.add(root);
        // 判断遍历的第N层是否有节点？
        while(!q.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            int n = q.size(); //取出这一层的节点数，不能在for循环取，因为会新加下一层节点
            for(int i=0;i<n; i++) { //逐个取出此层节点值，并新加下一层节点
                TreeNode node = q.poll();
                row.add(node.val);
                if(node.left!=null) {
                    q.add(node.left);
                }
                if(node.right!=null) {
                    q.add(node.right);
                }
            }
            res.add(row); 
        }
        return res;
    }
}